# What does VertexContract do?

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, {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, {{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.

• True, and surprising, this is not what one expects. Maybe the contraction of {1,2} lead to the new node three, contraction with {3,4} and after that {5,6} contracts to a single node. But this is not what I (one) would expect. – mgamer Sep 18 '16 at 22:06
• @mgamer I need this functionality, and I need it to work fast, so I exposed the corresponding function in IGraph/M. It will be in the next release. – Szabolcs Sep 19 '16 at 15:04
• I now had this problem, too. Making an example of the construction of the Petersen-Graph of tuples {I,j} with empty intersection to {k,l}. I did a ToString /@ VertexList[graph]... and similar for EdgeList. This than worked as expected (but up to now I did not do timing analysis - the PetersenGraph is not too large ;-) ) – mgamer Feb 15 '17 at 19:52

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!