# How to see if two graphs are the same (including node names)?

I want to check whether the two graphs are the same. With the same, I mean that they have the same edges and nodes.

For example, I want

SameGraph[
Graph[{{3, 4}, {1, 2}}],
Graph[{{1, 2}, {3, 4}}]
]
(* True *)


but

SameGraph[
Graph[{{3, 4}, {1, 2}}],
Graph[{{1, 5}, {3, 4}}]
]
(* False *)


Unfortunately, it seems that regular equality checking (both == and ===) in Mathematica somehow checks whether the edges were inputted in the same order so it would reject both of these graphs and only return true when I ask

SameGraph[
Graph[{{1, 2}, {3, 4}}],
Graph[{{1, 2}, {3, 4}}]
]
(* True *)


I found in the comments to this a reference to an IGSameGraphQ but this does not appear to exist in my installation of Mathematica.

• I have decided to delete my answer for now as I'm worried I am not fully grasping the question. If at all possible, could you come up with more test cases? My feeling is that if the adjacency matrices of the graphs are equal, then the graphs are equivalent because the same nodes are connected to each other. In the meantime, I will just leave my suggested SameGraph as a comment:  SameGraph[graphs_] :=With[{(adj = AdjacencyMatrix /@ graphs)}, Apply[Equal, adj] ]
– ydd
Commented Nov 13, 2023 at 15:44
• github.com/szhorvat/IGraphM
– Kuba
Commented Nov 13, 2023 at 16:06
• @ydd Your implementation requires the vertex ordering to be the same (i.e. doesn't treat the vertex set as a set), and does not compare vertex names. Commented Nov 13, 2023 at 18:22
• It is unfortunately not documented what == or === do for Graphs, even though the documentation actually uses these comparison operators in some examples. I requested these operations to be clearly defined several times, but there never was any reasonable response ... this is very frustrating. Commented Nov 13, 2023 at 18:25
• @Szabolcs Ah I see thanks.
– ydd
Commented Nov 13, 2023 at 21:23

The IGSameGraphQ function from the IGraph/M package will do this check. Vertex names are required to match, but edge/vertex ordering doesn't. Edge tags, if present, are not taken into account. Neither are any "annotations" such as edge weights.

You can also look at the source code of this function to see what a careful and reliable check requires. Naïve implementation of this check can very easily go wrong. I am actually very surprised that a build-in version of this is not available.

Try inputting the edges as a list of edges using:"[UndirectedEdge]" what displays as:

Then "EdgeList" can achieve what you want. Define e.g.:

check[g1, g2_] := (EdgeList@g1 // Sort) === (EdgeList@g2 // Sort)


Now with this we may check:

g1 = Graph[{3 \[UndirectedEdge] 4, 1 \[UndirectedEdge] 2}]
g2 = Graph[{1 \[UndirectedEdge] 2, 3 \[UndirectedEdge] 4}]
check[g1,g2]

True


And:

g1 = Graph[{3 \[UndirectedEdge] 4, 1 \[UndirectedEdge] 2}];
g2 = Graph[{1 \[UndirectedEdge] 5, 3 \[UndirectedEdge] 4}];
check[g1, g2]

False

• This does not work correctly when there are isolated vertices, or when edge tags are present, or when some undirected edges happen to be represented in the opposite order in one graph compared to the other. Commented Nov 13, 2023 at 18:16