graph with a cut vertex contains a bridge

1.7k Views Asked by At

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.

2

There are 2 best solutions below

0
On BEST ANSWER

For (a), take two cycles and join them at a vertex.

enter image description here

For (b), David's example of a forest with more than 1 tree in it works, as trees are connected by definition.

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.