# Determining if Graphs are Isomorphic.

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.

• @lhf Are two graphs isomorphic if they exhibit the same degree of nonexistence? Nov 10, 2015 at 1:05
• @lhf these are two separate questions. ;-) Nov 10, 2015 at 1:08
• @wbrugato also, I'm pretty sure that, even if the number of edges is fixed, there's no way they could be acyclic (it would imply tree implying 7 edges and degree 1 for at least 2 vertices) Nov 10, 2015 at 1:09
• Wait, are these two separate problems, 2 graphs in qn 1 and 2 graphs in question 2? Nov 10, 2015 at 1:10
• I believe its 2 graphs in question 1 and 2 graphs in question 2. Otherwise it doesn't work as a tree with 6 edges has 7 vertices.
– Ben
Nov 10, 2015 at 1:11

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.
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$.