Which Pair of these 3 graphs are is isomorphic

Question

I know that the 3 graphs have the same number of vertices and edges which is one of the condition for isomorphism . And I also know that having the same number of vertices and edges does not mean that they already isomorphic to each other. My question is, if there's pair in the graph that is isomorphic to each other, what is it and how I can prove it by mapping the vertices?

Answer 1

After you have verified that each graph contains a unique triangle, label each vertex of each graph with its distance from the triangle. That is, start by labeling the vertices of the triangle with $0$, then label their unlabeled neighbors with $1$, then label the unlabeled neighbors of those vertices with $2$, and so on.

When I did this I found that each graph has three vertices labeled $0$ (of course), and three vertices labeled $1$; but graph A has four vertices labeled $2$ and two vertices labelled $3$, while graph B has five vertices labeled $2$ and one vertex labeled $3$, and graph C has three vertices labeled $2$ and three vertices labeled $3$.

This means that no two of the three graphs are isomorphic.

Answer 2

The most general way to determine if a pair of graphs are not isomorphic is to use invariants. An invariant is a property of a graph that must be shared between all graphs that are isomorphic. For example, some simple invariants are:

• Number of vertices and edges
• Degree sequence
• Number of cycles of a particular size

The first is fairly obvious - two graphs cannot be isomorphic if they differ in the number of vertices or edges. The other two are slightly more complicated, but still obvious.

However, your set of three graphs share all these invariants. Since they are cubic (all vertices are degree 3), they have the same values for the first two invariants. The last one is harder to calculate, so here is another invariant:

• The extended degree sequence (aka 'signatures')

This is like the degree sequence, except we include the neighbours of the neighbours of each vertex. Essentially this gives us a tree rooted at each vertex, with the difficulty that we can end up visiting the same vertex twice. For example, this is the first graph from your example:

Here we have the graph on the left, and three trees on the right. Each tree is associated with a color (green, blue, orange) and the vertices of the graph are given colors from this set. When a vertex of the tree is duplicated - for example (12) in the first tree - then this is drawn with a square.

Note that the numbering is completely arbitrary. Also, the 'blue' vertices all have trees that are indistinguishable even though it is clear from the graph that they could be split further into at least {3, 4} and {5, 6, 7}.

Now compare this to the the extended degree sequence of the second graph:

Clearly we have the same number of colors (equivalence classes) and the same number of vertices with each color. However, the relations between the sets of colored vertices is different. In the second graph, there is no orange vertex connected to a green vertex.

These trees (signatures) can be extended further, to completely distinguish the vertices into classes. It can get more complex as the edges of cycles have to be traversed, but it is general.