Determining if Graphs are Isomorphic.

Question

Is it true that two graphs must be Isomorphic if:

1. They have 8 vertices, each with a degree of 3?
2. They are both connected, without cycles, and have 6 edges?

So I know that to be Isomorphic, each graph must have the same number of vertices connected in the same way. So for for the first question, I would have to show that a vertex might have a degree of 3 on one graph but not connect to the same three vertices as another, or that it must... I am confused on how to show this.

And my understanding for the second question, is that two connected graphs without cycles are pretty much a tree (?). I am confused on how to show these are/aren't isomorphic as well.

Any help/hints are appreciated.

Answer 1

The answer is no to both of them.

For $1$, consider $G$ to be two disjoint $K_{4}$'s. Then $G$ has $8$ vertices and all vertices have degree $3$. Let $H$ be $4$ copies of $K_{2}$ with multi-edges on each $K_{2}$ to satisfy the degree condition. These graphs aren't isomorphic.

You can also take an $8$-cycle and add chords in between the vertices to get another graph which you can use as a counterexample (if you like connected graphs).

for $2$, the question is asking if there are two different trees with $6$ edges. Take $P_{7}$ and any other tree which isn't a path and you have a counterexample.

Answer 2

Just give examples of non-isomorphic graphs satisfying the conditions. For #1, you could have on one hand a bipartite graph with 4 vertices in each part, and three edges at each vertex. On the other hand, you can have two copies of $K_4$.

For #2, just give two different trees with 6 edges! For instance, a path and a star.