Attempting to Disprove: If every vertex of G has degree 2, then G is a cycle
3,457
Your answer is perfect.
You may also wonder on this: Can you have a connected counterexample to this problem?
Related videos on Youtube
Author by
Admin
Updated on August 01, 2022Comments
-
Admin over 1 year
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.
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?
-
Sigur over 6 yearsCan $G$ be non connected?
-
Admin over 6 years@Sigur $G$ can be non-connected. $G$ must be finite.
-
-
Admin over 6 yearsI think that if $G$ must be connected graph and every vertex of $G$ has degree $2$, then it is true that then $G$ is a cycle. Am I correct?
-
Henrik supports the community over 6 years
-
Admin over 6 yearsWhy is the person who answers the question never always the person who comments first?
-
Arpan1729 over 6 yearsYou know why :P