Prove that the existence of a bridge is an invariant

428 Views Asked by At

An invariant is a property $P$ that is shared by all isomorphic graphs. In other words, a property $P$ is an invariant provided that whenever $G_1$ and $G_2$ are isomorphic graphs, if $G_1$ satisfies $P$, then $G_2$ also satisfies $P$.

A bridge is an edge $e$ whose removal yields a disconnected graph.

1

There are 1 best solutions below

0
On

Illustration: Below I generated a random connected graph (the blue graph) and highlighted it's bridges in orange. Then I relabeled the vertices of the graph to form the red graph below highlighted it's bridges in orange too.

A graph and an isomorphic graph

It's quite clear in the above example that bridges map to bridges and non-bridges map to non-bridges. The graph's structure has not changed. This is all isomorphism is, relabelling the vertices of the graph.

To prove that the existence of a bridge is a graph invariant formally, we should:

  • Let $G=(V,E)$ be an arbitrary graph with a bridge $ij \in E$. Let $\varphi$ denote a bijection with domain $V$. Show that $\varphi(i)\varphi(j)$ is a bridge in $\varphi(G)$.

  • Repeat the above for when $ij$ is a non-bridge.

Note: this proves the stronger (but unsurprising) result that the number of bridges is preserved under isomorphism.