If a connected graph has no bridges, does it contain a cycle?

I just started self studying graph theory through Springer's Combinatorics and Graph Theory. The following question was on the first chunk of exercises:

Prove or disprove: If G has no bridges, then G has exactly one cycle.

This is trivially false if G has no edges. However, I then asked myself the following questions:

If G is connected and has no bridges, does it have a cycle? Does it have exactly one?

In particular, this would give as a corollary a later exercise asking to prove that every 2-connected graph contains at least one cycle. To the first question, I think the answer is positive by the following reasoning:

If G is connected, take a pair of adjacent vertices $u-v$. Since $uv$ is not a bridge, if we take it away there will still be a path joining the vertices. Now take this path plus $uv$ and you'll have a cycle.

I think the second question has negative answer, and a counterexample would be two polygon cycles with one "tangent" vertex.

Are these answers correct, and if so, is there a more organic graph theoretical way to phrase them?

• You are on the right track.
– hbm
Commented Jan 19, 2014 at 3:40
• There is a connected graph with no bridges and no cycles: the graph with only one vertex and no edges. However, if the graph is connected, without bridges and has at least two vertices, then indeed it must have a cycle. Commented Jan 19, 2014 at 4:03

The answer to the first question is obvious NO, since the complete graph on at least $4$ vertices has no bridges, and boatloads of cycles. For the other question, suppose the graph has no cycles (so is a tree), then it obviously has a bridge. The contrapositive of which is that if a (connected, as always) graph has no bridge, then it has a cycle.