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.
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$.