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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.