# Determine which are true and which are false | Graph Theory

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.

• Can you provide definitions for: - cutting edge - cutting vertex - disconnected bipartite Commented Apr 1, 2021 at 1:23
• @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. Commented Apr 1, 2021 at 1:31
• 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? Commented Apr 1, 2021 at 1:37
• 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? Commented Apr 1, 2021 at 1:38
• 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)$. Commented Apr 1, 2021 at 1:47

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)$$.