# Cut edge and cut vertex

Let $G$ be simple graph and $G$ has a cut edge. Does $G$ have a cut vertex?

Exercise 2.3.1 from the book Graph Theory with Applications by Bondy and Murty.

-

ORIGINAL (FLAWED) PROOF

Without loss of generality, let $G$ be connected. Let $e$ be a cut-edge with endpoints $u$ and $v$. Since $e$ is a cut-edge, its removal would separate $G$ into two components $H_1$ and $H_2$. This means that every path from a vertex in $H_1$ to a vertex in $H_2$ passes through $e$, and so every such path passes through both $u$ and $v$. Therefore, both $u$ and $v$ are cut-vertices.

As Joseph mentioned in the comments, a pendant edge is always a cut-edge, while a leaf cannot be a cut-vertex. Thus, the only way that both $u$ and $v$ fail to be cut-vertices is thus the case when $G$ is a single edge.

REVISED PROOF

Without loss of generality, let $G$ be connected. Let $e$ be a cut-edge with endpoints $u$ and $v$.

Note that if a vertex is a leaf, it cannot be a cut-vertex, since its removal does not increase the number of components of $G$. Thus, if $e$ is the only edge of $G$, then both $u$ and $v$ are leaves, and so $G$ possesses no cut-vertex.

Assume now that $G$ contains another edge $f$ distinct from $e$. Since $e$ is a cut-edge, its removal would separate $G$ into two components $H_u$ and $H_v$. This means that every path from a vertex in $H_u$ to a vertex in $H_u$ passes through $e$, and so every such path contains both $u$ and $v$. Now, one of $H_u$ or $H_v$ contains a vertex other than $u$ or $v$ (respectively), as $f$ belongs to one of these two components. Therefore, one of $u$ or $v$ is a cut-vertex. Furthermore, if neither $u$ nor $v$ is a leaf, then both $u$ and $v$ are cut-vertices.

-
it is true for connected case.but can you I'm interested in 2.3.1-b.can you take example for this case(disconnected). – Babak Miraftab Jul 21 '11 at 5:56
For any graph G, you can consider its connected components and reduce to Austin's explanation above. – Daniel Freedman Jul 21 '11 at 8:42
no,I'm looking for answer of exercise 2.3.1-b – Babak Miraftab Jul 21 '11 at 9:33
What is the exercise? – Daniel Freedman Jul 21 '11 at 9:47
What happens if the graph consists of exactly two vertices joined by an edge? – Joseph Malkevitch Jul 21 '11 at 14:28