How to demonstrate every vertex N and edge(U,V) belong to common cycle?

79 Views Asked by At

Let $G = (N, E)$ be a connected undirected graph such that for every pair of vertices $u$ and $v$, there are at least two vertex-disjoint $(u,v)$-paths.

How can we show that for every vertex $n\in N$ and edge $uv\in E$, there exists a cycle containing the vertex $n$ and the edge $uv$?

1

There are 1 best solutions below

0
On

Graphs with the mentioned property are called 2-connected or biconnected.

Make a new graph $G^*$ by adding a new vertex $w$, which is adjacent to $u$ and $v$ only.

The graph is still $2$-connected (this is more clear from other definitions of $2$-connectedness, but we could prove it if needed from the definition given), so there must be at least two vertex-disjoint $wn$-paths. Since $n$ only has two neighbors, and since the two paths are vertex-disjoint, then one path must go through $u$ and the other must go through $v$. If we take the union of these two paths, remove the edges $uw$ and $vw$, and add the edge $uv$, then we have a cycle that contains the edge $uv$ and the vertex $n$. QED