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.

  • $\begingroup$ @lhf Are two graphs isomorphic if they exhibit the same degree of nonexistence? $\endgroup$ – Mitch Nov 10 '15 at 1:05
  • $\begingroup$ @lhf these are two separate questions. ;-) $\endgroup$ – Nick Matteo Nov 10 '15 at 1:08
  • $\begingroup$ @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) $\endgroup$ – Mitch Nov 10 '15 at 1:09
  • $\begingroup$ Wait, are these two separate problems, 2 graphs in qn 1 and 2 graphs in question 2? $\endgroup$ – Mitch Nov 10 '15 at 1:10
  • $\begingroup$ 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. $\endgroup$ – Ben Nov 10 '15 at 1:11

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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.