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.
Best Answer
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.