What does VertexContract do?

Question

From the documentation,

VertexContract[g, {v1, v2, ...}] contracts a collection of vertices v1, v2, ... into a single vertex of the graph g.

Let's try it:

VertexContract[CycleGraph[6], {3,4}] // EdgeList

(* {1 <-> 2, 1 <-> 6, 2 <-> 3, 5 <-> 6, 5 <-> 3} *)

Vertices 3 and 4 were contracted into a single vertex now named 3. Effectively we have a cycle on vertices 1, 2, 3, 5, 6. So far so good.

VertexContract[g, {{v1, v2, ...}, ...}] contracts several collections of vertices.

I am not getting this one. I expected

VertexContract[CycleGraph[6], {{1, 2}, {3, 4}, {5, 6}}]

to contract the pairs {1,2}, {3,4} and {5,6}, each, and get this graph:

{1 <-> 3, 3 <-> 5, 5 <-> 1}

I.e. a cycle on 1, 3, 5.

Instead I get a graph with a single vertex and no edges. Why? What does this command actually do?

---

I can do

Fold[VertexContract[#1, #2] &, g, {{v1, v2, ...}, ...}] 

to achieve the result I expected, but it's pretty slow when there's a lot to contract.

Answer 1

It looks as if there is no difference between passing a list of lists and the same vertices in a single list. To check this, I try a variety of random cases

test := Module[{n, m, p, q, g, list, g1, g2},
  n = 100;
  m = 300;
  p = RandomInteger[{2, 5}];
  q = RandomInteger[{2, 5}];
  g = RandomGraph[{n, m}];
  list = RandomChoice[VertexList[g], {p, q}];
  g1 = VertexContract[g, list];
  g2 = VertexContract[g, Flatten[list]];
  g1 === g2]

I have never seen the test fail

And @@ Table[test, 1000]
(* True *)

Obviously, this is not absolute proof, but if there were some subtle difference one might expect the documentation to make it a little clearer!