CMI2019-B-4

Question

Consider the assertion: Any connected undirected graph $G$ with at least two vertices contains a  vertex $v$ such that deleting $v$ from $G$ results in a connected graph. Either give a proof of the assertion, or give a counterexample (thereby disproving the assertion).

Answer 1

This assertion is true.
Let's try to prove this by "Proof By Contradiction Method".

Let's assume, Any connected undirected graph G with at least two vertices "do not contains"
 a vertex v such that deleting v from G results in a connected graph.

Now,

Assume vo, v1, v2,....Vn be the longer path in the graph G.

Let's say one vertex among these went to the set of vertices of one of the connected components of the graph (in case there is an articulation point)

But then one of the longer path in the other connected component will contain one of these vertex, which contradicts the fact that v0, v1, v2...Vn was the longer path.

This contradicts the fact what we assumed.

This proves that the given assertion is true.

Comments

This proof should have been written in much more detail.

Answer 2