stylaria3y

2022-07-18

Nonisomorphic graphs Discrete Math
Find 3 different nonisomorphic graphs with 8 vertices that have the degree sequence 2,2,2,2,2,2,2,2. Answer: An 8-cycle, or two 4-cycles, or a 3-cycle and a 5-cycle.
Can someone show me how these three answers were found? I am a little confused with nonisomorphic graphs. I used to think you could just change the name of each vertex because no matter how you rearranged the vertices they would never be able to be rearranged back to their previous form. But then I was wrong and was told that you have to pay attention to adjacency but how? So for this question, how did the person come by these three answers?

Eve Good

Step 1
Changing the names of the vertices results in an isomorphic graph, of course: the isomorphism sends each vertex to itself under its former name.
Two graphs are isomorphic if there's any bijection between vertices which always takes an edge to an edge; in other words, a bijection of the vertices that preserves adjacency, as you mentioned. It means that it's possible to draw the two graphs the same way.
For instance, on a given set of eight vertices, there are going to be $\left(\genfrac{}{}{0}{}{8}{5}\right)\frac{4!}{2}=672$ different graphs consisting of a 5-cycle and a 3-cycle; but all of them are isomorphic. Suppose G and H are two such graphs. Say the vertices on the 5-cycle in G, in cyclic order, are ${v}_{1},{v}_{2},{v}_{3},{v}_{4},{v}_{5}$, and the vertices on its 3-cycle are ${v}_{6},{v}_{7},{v}_{8}$, while the vertices in H are ${w}_{1},{w}_{2},{w}_{3},{w}_{4},{w}_{5}$ on the 5-cycle and ${w}_{1},{w}_{2},{w}_{3}$ on the 3-cycle. Then mapping ${v}_{i}↦{w}_{i}$ is an isomorphism.
Step 2
Coming to these three kinds of 2-regular 8-vertex graphs isn't too hard, if you know this fact:
If every vertex has degree two, then the graph consists of disjoint cycles (or infinite chains.)So, how can you possibly break 8 vertices into cycles? It seems that the definition you use for "graph" doesn't allow multiple edges or loops, so that a cycle must have at least three vertices.

Do you have a similar question?