Let $G$ be A simple connected graph such that all degrees are at least $2$. Is it true that every vertex is on a circle ?


It's not true. A counter example would be two disjoint cycles plus one connecting edge. The connecting edge is not part of any cycle.

Edit: To get a vertex that is not on a cylce one can modify the example above by putting an extra vertex in the middle of the connecting edge.

  • $\begingroup$ but i meant vertices, not edges $\endgroup$ – boaz Sep 11 at 11:12
  • $\begingroup$ still, in a circle we can visit a vertex twice, so your example does not contradicts the assertion. $\endgroup$ – boaz Sep 11 at 14:11

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.