Proof of the lemma: $3$-connected graph with $|V(G)| > 4$ has an edge $e$, such that $G/e$ is $3$-connected

95 Views Asked by At

In Diestel's Graph Theory (3rd edition), the following proof of the mentioned lema is provided:

actual screenshot from the book

What I cannot wrap my head around is how it is obvious that $D \subseteq C$. What about other vertices from $D$ that are not adjacent to $v$? This matter is not elaborated, so my guess is that I'm missing something crucial, but I'm unable to find what.

1

There are 1 best solutions below

0
On BEST ANSWER

I think I figured it out with the help of the Google preview of the 5th edition of Diestel's Graph Theory book, which contains an updated figure $3.2.1.$ From the right side of the figure it is quite obvious that $D \subseteq C$ holds, since removing $\{x,y,z\}$ leaves $v$ connected to $D$ and we know that $v \in C$. Then, $v \in C$ and $v \notin D$ implies $D \subset C$.

Image from the 5th edition of Graph Theory