3
$\begingroup$

As title, (note: this questions is asking weather or not all vertices are contained IN a cycle not asking if the G contains a cycle.

My attempt is that: enter image description here

So this graph would be an counter example that disprove that every vertex is contained in a cycle. Would like to know if this is a valid counter-example since V1 is not contained in a cycle.

PS: As I was finding examples, also observed that if the all V have exactly degree of 2, then it is necessary that all vertices are contained in a cycle. Please prove if I am missing something.

|cite|improve this question
$\endgroup$
1
$\begingroup$

You are asking two questions. The first question is whether your graph is a counterexample to the claim that in a graph with minimum degree 2, every vertex lies in a simple cycle. Unfortunately, your graph is not simple, so if by graph you mean simple undirected graph, then your graph is not a counterexample. However, if you replace the self-loop by a cycle, you should get a valid counterexample.

The second question is whether the claim is true if the graph is 2-regular (all degrees are 2). Indeed, a 2-regular graph is a disjoint union of cycles. I'll leave you to figure out a proof.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Just curious, what if the self-loop is not replaced by a cycle, what kind of graph would be satisfied with such attempted counter-example ?( completed graph ?) (no offense, just would like to learn a bit more ) $\endgroup$ – ScsD Oct 2 '18 at 4:48
  • $\begingroup$ Any graph with minimum degree 2 in which not every vertex lies in a simple cycle would work. $\endgroup$ – Yuval Filmus Oct 2 '18 at 5:35

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.