0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ What are your thoughts about this? You could at least start with defining the terms used in the statements. $\endgroup$
    – user694818
    Nov 19, 2019 at 14:17

2 Answers 2

0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ For (a), you can have cut-vertices without bridges. For example if vertex connectivity is 1 and edge connectivity is 2, you have a cut-vertex but no bridge. $\endgroup$ Apr 27, 2020 at 11:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .