1
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ It's true. In fact, the graph with one vertex is sometimes considered disconnected. $\endgroup$
    – Pål GD
    Jun 6, 2018 at 20:35
  • $\begingroup$ So why do you doubt your answer? $\endgroup$
    – Juho
    Jun 6, 2018 at 21:12
  • $\begingroup$ @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. $\endgroup$
    – Thinker
    Jun 7, 2018 at 10:11
  • $\begingroup$ @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? $\endgroup$
    – Thinker
    Jun 7, 2018 at 10:14
  • 1
    $\begingroup$ @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. $\endgroup$
    – Pål GD
    Jun 7, 2018 at 14:52

1 Answer 1

3
$\begingroup$

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.
$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$
    – Thinker
    Jun 9, 2018 at 11:31
  • 1
    $\begingroup$ @Thinker I answered you in an extra note in the answer. $\endgroup$
    – Pål GD
    Jun 9, 2018 at 18:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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