MathsGee is Zero-Rated (You do not need data to access) on: Telkom |Dimension Data | Rain | MWEB

0 like 0 dislike
39 views
What is a bridge in graph theory?
| 39 views

0 like 0 dislike
An edge e of G is called a bridge if G-e has more components than G.

NB: This definition implies that if G is connected, then G-e is disconnected.

Lemma:
Let G be a connected graph. For some $x, y \in V(G)$, if $e=\{x, y\}$ is a bridge, then G-e has precisely 2 components; Furthermore, x and y are in different components.

Theorem:
An edge e is a bridge of a graph G iff it is not connected in any cycle of G.

Corollary:
If there are 2 distinct paths from vertex u to vertex v in G, then G contains a cycle.
by Diamond (81,058 points)

0 like 0 dislike
0 like 0 dislike
0 like 0 dislike
0 like 0 dislike