1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user145640 Apr 26 at 14:28
  • 1
    $\begingroup$ @user145640 So take the cycle going through all the vertices. $\endgroup$ – Misha Lavrov Apr 26 at 14:40
  • $\begingroup$ @MishaLavrov Good point! $\endgroup$ – user145640 Apr 26 at 14:44
1
$\begingroup$

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

$\endgroup$

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.