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.

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.

share|improve this question
add comment

1 Answer

up vote 5 down vote accepted

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.

ADDENDUM

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.

share|improve this answer
    
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
3  
What is the exercise? –  Daniel Freedman Jul 21 '11 at 9:47
2  
What happens if the graph consists of exactly two vertices joined by an edge? –  Joseph Malkevitch Jul 21 '11 at 14:28
show 2 more comments

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.