# How does Mathematica calculate its AdjacencyMatrix[ ] and VertexDegree[ ]

I define a graph:

g = Graph[{1 \[UndirectedEdge] 3, 2 \[UndirectedEdge] 4,
3 \[UndirectedEdge] 4, 3 \[UndirectedEdge] 5,
4 \[UndirectedEdge] 5, 5 \[UndirectedEdge] 6},
VertexLabels -> "Name"]


The output looks correct in how the vertices are connected, but the AdjacencyMatrix[g] and VertexDegree[g] put the vertices out of order with my labels.

Why is that, and what is the order Mathematica uses?

• Vertex ordering is completely unrelated to the names of the vertices. Vertices can be any expression, not just numbers. Never assume that numerical vertices are ordered from smallest to greatest. Use VertexIndex and VertexList to relate the index of a vertex to the vertex itself. In practice, Mathematica puts the vertices in the order you first specify them (as they appear in the edge list in your example), but never count on this as there's no guarantee and I won't be surprised if future versions change this. – Szabolcs May 25 '15 at 8:52
• I removed the implementation-details tag because the question is more about what the function returns than about how the function works internally. – Szabolcs Aug 3 '15 at 15:21

So, unless you provide a vertex list as the first argument of Graph, VertexList[g] is populated with vertices in the order they appear in the edge list, i.e., {1, 3, 2, 4, 5, 6}. Using Range[6] as the first argument in Graph:

g1 = Graph[Range[6], {1 \[UndirectedEdge] 3, 2 \[UndirectedEdge] 4,
3 \[UndirectedEdge] 4, 3 \[UndirectedEdge] 5,
4 \[UndirectedEdge] 5, 5 \[UndirectedEdge] 6},
VertexLabels -> "Name", ImagePadding -> 10]


versus

g2 = Graph[{1 \[UndirectedEdge] 3, 2 \[UndirectedEdge] 4,
3 \[UndirectedEdge] 4, 3 \[UndirectedEdge] 5,
4 \[UndirectedEdge] 5, 5 \[UndirectedEdge] 6},
VertexLabels -> "Name", ImagePadding -> 10]


Their VertexLists and VertexDegrees:

Column[Labeled[TableForm[{VertexList@#, VertexDegree@#},
TableHeadings -> {{"VertexList", "VertexDegree"}, None}], #2,
Top] & @@@ {{g1, "g1"}, {g2, "g2"}}, Spacings -> 2]


and AdjacencyMatrixs:

Row[Labeled[TableForm[Normal@AdjacencyMatrix@#,
TableHeadings -> {VertexList@#, VertexList@#}],
#2, Top] & @@@ {{g1, "g1"}, {g2, "g2"}}, Spacer[15]]