1
$\begingroup$

I was wondering how to solve this problem.

The idea is something along these lines if there are more edges than vertices (or equal), you have a cycle.

Since this is only possible with Graphs of order $3$ or more, we have a cycle of $3$ or more.

This means that you could take any of those edges out, and the graph is connected.

Making it not a bridge. Am I right?

$\endgroup$
2
  • 3
    $\begingroup$ Yes, that's correct. $\endgroup$ Sep 19, 2020 at 12:04
  • $\begingroup$ Try to consider some cycle $C$ in graph $G$. What can you say about the graph obtained from $G$ by deleting one of the edges of $C$? $\endgroup$
    – richrow
    Sep 19, 2020 at 18:08

1 Answer 1

0
$\begingroup$

As stated when we have an undirected graph of more than/equal to edges, there exist cycles since you have to have an extra connection somewhere. This can be removed, making it not a bridge.

$\endgroup$

You must log in to answer this question.

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