Give a counter example to each of the following:
(a) G is a connected graph with a cut-vertex, then G contains a bridge.
(b) G is a tree if and only if it contains no cycle.
2026-05-16 00:16:57.1778890617
On
graph with a cut vertex contains a bridge
1.7k Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
2
There are 2 best solutions below
1
On
For $(a)$, there are no counterexamples. this is a consequence of vertex connectivity being less than or equals to the edge connectivity.
For $(b)$, if we don't assume $G$ connected, any forest (union of trees) with more than one component will work. Note the definition of tree is a connected graph with no cycles.
For (a), take two cycles and join them at a vertex.
For (b), David's example of a forest with more than 1 tree in it works, as trees are connected by definition.