# Finite Graph With Degree $\geq 2$

Show that a finite graph with all vertices with degree $$\geq 2$$ has a cycle that contains a vertex which is non-adjacent to any other vertices not contained in the cycle.

I tried to start at an arbitrary 𝑣∈𝑉 and let 𝑃 be a maximal path beginning at 𝑣. and then let 𝑢 be the endpoint of 𝑃. then all neighbors of 𝑢 must be in 𝑃 because all neighbors of P has degree larger than 2, meaning that maximal path can go around all neighbors before ending at P. Then somehow i close the loop of this maximal path and have this cycle? How would i do that.

• Unless I'm reading this wrong or missing something, this seems extremely false. An obvious counterexample is a complete graph. Then every vertex of every cycle is adjacent to all other vertices not in the cycle. – user145640 Apr 26 at 14:28
• @user145640 So take the cycle going through all the vertices. – Misha Lavrov Apr 26 at 14:40
• @MishaLavrov Good point! – user145640 Apr 26 at 14:44

To close the loop, take the edge from $$u$$ to its earliest neighbor of $$P$$: the one that is furthest from $$u$$ and closest to $$v$$. Then follow $$P$$ back to $$u$$. Throw away the portion of $$P$$ before any of $$u$$'s neighbors.
Now all the neighbors of $$u$$ are on this cycle, because all of them were on the path $$P$$ to begin with - and since we went back to the earliest of them, we'll see all the others when we follow $$P$$ back to $$u$$.