Attempting to Disprove: If every vertex of G has degree 2, then G is a cycle

4.2k Views Asked by At

According to http://www.sfu.ca/~mdevos/345/homework1_sol.pdf, the statement

If every vertex of G has degree 2, then G is a cycle

is a false statement.

I have attempted to draw a counter example attached as jpeg to confirm that we have a false statement. Counterexample

Orange dots represent vertices. Black lines are edges. $H_1$ and $H_2$ are names of the subgraphs of $G$. The union of $H_1$ and $H_2$ is graph $G$. Every subgraph of $G$ has vertices of degree equal to two, so every vertex of $G$ has degree 2. However, $G$ is not cyclic.

Is my counterexample correct?

1

There are 1 best solutions below

4
On BEST ANSWER

Your answer is perfect.

You may also wonder on this: Can you have a connected counterexample to this problem?