3
$\begingroup$

Prove that a simple undirected graph $G$ is a path if and only if $G$ has exactly two vertices which are not cut-vertices.

If $G$ is a path then it is obvious that there only two vertices which are not cut-vertices. These vertices are the endpoints of the path.

For the converse here it is what I did:

Suppose that $G$ has exactly to vertices $u,v$ which are not cut-vertices. Let $P_{uv}$ a maximal $(u,v)-\text{path}$. Since the path is maximal all the neighbours of $u$ and $v$ lie on the path $P_{uv}$.

I tried to prove that every vertex of $G$ lies on the path but I am stuck.

Any help?

1 Answers 1

4

Let $a$ and $b$ be the endpoints of an arbitrary maximal path $P$ in $G$. Then all neighbours of $a$ and $b$ lie in $P$.

It is easily seen that $a$ and $b$ are not cut-vertices: If $x$ and $y$ are vertices connected through a path $P' = x \dots v a v' \dots y$, we can always find a new path which doesn't contain $a$ but connects $x$ and $y$ (this is because $v,v' \in P = a v_1 \dots v_k b$). Similarly for $b$. Because $a$ and $b$ are the only two 'non-cut-vertices' in $G$, we conclude that every maximal path $P$ in $G$ must have $a$ and $b$ for its endpoints. It follows that $G$ is connected: for every vertex $v$ there is a maximal path $P_v$ that contains $v$ and its endpoints are $a$ and $b$.

Now, let $P=a v_1 v_2 \dots v_k b$ be a maximal path and suppose there exists a vertex $x \notin P$. Because $x$ is a cut-vertex $G \setminus \{x\}$ has at least two connected components: $P \subset C_1$ and $y \in C_2$, $C_1 \cap C_2 = \varnothing$. But in $G$, there exists a path $P_y = a \dots y \dots b$. The vertex $x$ can't be at the same time in the first 'half' $a \dots y$ and the second 'half' $y \dots b$ of the path $P_y$, for example $x \notin a \dots y$. Then $a \dots y \subset G \setminus \{x\} \implies y \in C_1$ which is a contradiction.

  • 0
    Thank you very much for your time! Nice solution!!!2012-11-16