0
$\begingroup$

From the following statements determine which are true and which are false. In each case justify your answer or give a counterexample.

a) If a connected graph has cut vertices, then also it has bridges.

b) If in a connected graph there are two cut edges that affect in the same vertex $u$, then $u$ is a cut vertex.

c) If in a connected graph every edge is a bridge then $G$ has cycles.

d) If $G$ is disconnected and bipartite then each component of $G$ is bipartite.

e) If in a graph $G$ the degree of each vertex is even then $G$ has bridges.

I have some ideas for the exercise (but I don't know if they are correct) ... For (a) it is not true in general. Let's consider two cycles together so that they have a common vertex, then we have a cut vertex but not a bridge. For (c) it is not true in general. Consider the star graph of order 4, $ S_4 $. Every edge is a bridge, but it does not contain cycles. For (e) it is not true in general. If we consider the cycle graph of order 3, $ C_3 $, we note that the degree of each vertex is even, but the graph has no bridges. For (d) I'm sure it's true, but I don't know how to explain it. And for the rest, I don't know.

$\endgroup$
8
  • $\begingroup$ Can you provide definitions for: - cutting edge - cutting vertex - disconnected bipartite $\endgroup$ Apr 1, 2021 at 1:23
  • $\begingroup$ @JackNeubecker Let $G$ be a connected graph. A vertex $v \in G$ is called a cut vertex of $G$, if $G-v$ (Delete $v$ from $G$) results in a disconnected graph. Removing a cut vertex from a graph breaks it in to two or more graphs. A bridge or cut-edge, is an edge of a graph whose deletion increases the graph's number of connected components. Equivalently, an edge is a bridge if and only if it is not contained in any cycle. $\endgroup$
    – Kitty M.
    Apr 1, 2021 at 1:31
  • $\begingroup$ So a cutting edge is just a cut-edge, and a cutting vertex is just a cut-vertex? There is no reason to use two different jargon words for the same object. How about disconnected bipartite, is this just disconnected and bipartite? $\endgroup$ Apr 1, 2021 at 1:37
  • $\begingroup$ A disconnected bipartite, as it would be an disconnected bipartite graph. That is, there is at least one vertex that is not connected. Explain me? $\endgroup$
    – Kitty M.
    Apr 1, 2021 at 1:38
  • 1
    $\begingroup$ Is there any special meaning to saying $u$ is the cut-vertex? It is easy to construct an example where it is not the only cut-vertex. But it is a cut vertex, as by removing $u$ you also remove the two cut-edges adjacent to $u$. By the fact they are cut-edges, this disconnects the graph. As for (d), consider the partition of $V(G)$, namely $V_1$ and $V_2$. Then consider any connected component $C$. $V_1 \cap V(C)$ and $V_2 \cap V(C)$ partitions $V(C)$, and by definition, there are no edges between $V_1$ and $V_2$, so no edges between $V_1 \cap V(C)$ and $V_2 \cap V(C)$. $\endgroup$ Apr 1, 2021 at 1:47

1 Answer 1

2
$\begingroup$

b) True: $V - u$ does not contain the edges adjacent to $u$. As these edges are cut-edges, $V - u$ is disconnected. Thus, $u$ is a cut-vertex. It is not unique however.

d) True: Consider the partition of $V(G)$, namely $V_1$ and $V_2$. Then consider any connected component $C$. $V_1 \cap V(C)$ and $V_2 \cap V(C)$ partitions $V(C)$, and by definition, there are no edges within $V_1$ or $V_2$, so no edges within $V_1 \cap V(C)$ or $V_2 \cap V(C)$.

The counterexamples you give for a,c,e are correct.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .