0
$\begingroup$

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.

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

2 Answers 2

Reset to default
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .