Prove that if removing 3 vertices from a connected graph results in a connected graph, then there exists a 3-fan to those 3 vertices

105 Views Asked by At

This is a proposition from lecture that I'm trying to prove: enter image description here

However, consider the following graph

enter image description here

where set A is indicated by the yellow vertices. If we remove this set from the graph B, then B - A is still connected. However, we can't choose any vertex x in V(B)\A such that there is a 3-fan from x to A. This is obvious, because one of the vertices in A is only accessible through the other two vertices, so there can't be a fan to that group of vertices.

Am I misunderstanding the Lemma here, or is it incorrect? If it is correct, how would I prove it?

Thank You

Edit: The above lemma was incorrect. It was meant to be that all vertices in A must be adjacent to a vertex in V(B)\A. The proof is enter image description here

1

There are 1 best solutions below

0
On BEST ANSWER

I agree with your understanding of Lemma and counterexample. So I think there is something wrong with Lemma formulation.