Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
Thank you very much for your time! Nice solution!!! –  passenger Nov 16 '12 at 14:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.