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$
    – Parcly Taxel
    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

Reset to default
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$

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.