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?

Share:
3,457

Related videos on Youtube

Admin
Author by

Admin

Updated on August 01, 2022

Comments

  • Admin
    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. 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?

    • Sigur
      Sigur over 6 years
      Can $G$ be non connected?
    • Admin
      Admin over 6 years
      @Sigur $G$ can be non-connected. $G$ must be finite.
  • Admin
    Admin over 6 years
    I 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
    Henrik supports the community over 6 years
  • Admin
    Admin over 6 years
    Why is the person who answers the question never always the person who comments first?
  • Arpan1729
    Arpan1729 over 6 years
    You know why :P