TU Wien:Diskrete Mathematik für Informatik VU (Drmota)/Übungen WS20/Beispiel 5

A cut edge is an edge whose removal increases the number of components. Show that an edge is a cut edge if and only if it does not belong to any cycle.

Lösungsvorschlag

Take a Graph $G=(V,E)$. Let $e\in E,e=\{u,v\}$ with $v,u\in V$
1.) Show that if e is a cut edge, then e is not in a cycle.
Assume that e is in a cycle. If e is removed, then there still exists a path from u to v (via the "other" part of the cycle) --> u,v are still part of the same component --> e cannot be a cut edge.
2.) Show that if e is not in a cycle, then e is a cut edge.
Assume that e is not a cut edge. If it is removed from the graph, u,v still need to be connected. This would mean that there is another path from u to v --> There exists a cycle --> e is part of a cycle

=> An edge is a cut edge if and only if it does not belong to a cycle.