# Certainty of the New Vertex Name after using EdgeContract

It appears that when I use EdgeContract on an undirected graph, the vertex that is the result of contracting an edge is always named the smaller of the two vertices. So

VertexList@EdgeContract[g, UndirectedEdge[1,3]]


will no longer contain the vertex 3. Is it guaranteed anywhere in the Mathematica documentation that this will always be the behavior of EdgeContract (at least on an undirected graph where we contract a single vertex)? I couldn't find any mention of this on the documentation page for EdgeContract. I would hate to be surprised by some subtly in how EdgeContract is implemented where it renames the vertices some other way.

Yes, it is always the case that EdgeContract replaces the vertices appearing in the contracted edges with the "smallest" vertex.

The function EdgeContract calls the function GraphComputationGraphContractDumpedgeContract which takes the Union of the vertices appearing in the contracted edges (see the highlighted lines below) and calls VertexContract,

and

Example:

VertexList[EdgeContract[Graph[{1 <-> 2, 3 <-> 1, 1 <-> 4, 1 <-> 5, 1 <-> 6, 1 <-> 7,
2 <-> 3, 2 <-> 7, 3 <-> 4, 5 <-> 4, 5 <-> 6, 6 <-> 7}],
{UndirectedEdge[6, 7], UndirectedEdge[5, 4]}]]


{1, 2, 3, 4}

Temporarily replacing Union with DeleteDuplicates we get

Block[{Union = DeleteDuplicates},
VertexList[EdgeContract[Graph[{1 <-> 2, 3 <-> 1, 1 <-> 4, 1 <-> 5, 1 <-> 6, 1 <-> 7,
2 <-> 3, 2 <-> 7, 3 <-> 4, 5 <-> 4, 5 <-> 6, 6 <-> 7}],
{UndirectedEdge[6, 7], UndirectedEdge[5, 4]}]]]


{1, 2, 3, 6}

Note: See the answers by Simon Woods and Taliesin Beynon in Spelunking tools for useful ways to get the definitions of Mathematica functions.

• Wow. Thank you very much. Commented Mar 2, 2016 at 17:07
• @mapierce271, my pleasure. Thank you for the Accept.
– kglr
Commented Mar 2, 2016 at 17:10