# If a connected graph has a bridge then it has a cut vertex

Is it true that if a connected graph has a bridge then it has a cut vertex?

In my point of view, I don't think it is true to consider that a graph having a cut edge will definitely have cut vertex.

Consider a graph with a single edge $uv$; if we remove this edge, the graph will get disconnected but if we remove $u$, the graph will be connected as a graph with the single vertex is still consider connected.

• It's true. In fact, the graph with one vertex is sometimes considered disconnected. – Pål GD Jun 6 '18 at 20:35
• So why do you doubt your answer? – Juho Jun 6 '18 at 21:12
• @juho because if I answer wrong then in competitive exams I will be rewarded with negative marking :-) and secondly it is always better to discuss with a smart community. – Thinker Jun 7 '18 at 10:11
• @Pål GD if we take vertex connectivity into the picture then single vertex will be a trivial graph and is considered to be disconnected right? – Thinker Jun 7 '18 at 10:14
• @DavidRicherby It comes from $k$-connectivity, in which you require the graph to have more than $k$ vertices. By that definition ("a 1-connected graph is called connected"), $K_1$ is disconnected by having too few vertices. – Pål GD Jun 7 '18 at 14:52

An edge $e=uv$ is a bridge in $G$ if there is no path between $u$ and $v$ in $G-e$.

In general, $u$ and $v$ are cut vertices, but there are some special cases you must treat with care.

(1) If $G \simeq K_2$, then depending on the definition of connectivity, the $G-u \simeq K_1$ might and might not be considered connected*.

(2) There is another case in which you would not consider $u$ to be a cut vertex; An edge $uv$ is called a pendant edge if $\deg(u) = 1$. In this case, if $uv$ is a pendant edge and $\deg(v)>1$, you would not typically call $u$ a cut vertex.

Postlude

All that being said, definitions in graphs are hard (case in point: Diestel). When we try to make definitions very general, special cases sometimes become absurd.

Note

1

* To address David Richerby's objection, $K_1$ is considered disconnected when deriving connectivity from k-connectivity, in which you require the graph to have more than $k$ vertices. By that definition ("a 1-connected graph is called connected"), $K_1$ is disconnected by having too few vertices.

2

To answer Thinker's follow-up question; since you wanted to know what to answer to a hypothetical exam question, I would do it this way:

Let $e = uv$ be a bridge. We have three cases:

1. $\deg(u), \deg(v) > 1$. The statement is true.
2. $\deg(u) = 1, \deg(v) > 1$. The statement is true, $e$ is a pendant.
3. $\deg(u) = \deg(v) = 1$. The statement is true if and only if $K_1$ is considered connected.
• So the statement, if a connected graph has a bridge then it has a cut vertex, does not hold for K2(a complete graph with 2 vertices ). by connected I mean 1-connected – Thinker Jun 9 '18 at 11:31
• @Thinker I answered you in an extra note in the answer. – Pål GD Jun 9 '18 at 18:17