Scribd
Upload
39 views9 pages

2-Connected 3 Guia

This document defines and discusses 2-connected graphs through several lemmas and theorems: - A graph is 2-connected if it remains connected after removing any single vertex. Equivalently, for any two vertices there exist two internally disjoint paths between them. - Whitney's theorem states that if a graph with at least three vertices is 2-connected, then for any two vertices there exist internally disjoint paths between them. - A characterization theorem establishes that several graph properties are equivalent to a graph being 2-connected, including having internally disjoint paths between all vertex pairs and every pair of edges lying on a common cycle.

Uploaded by

Semy Zambrano
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
39 views9 pages

2-Connected 3 Guia

This document defines and discusses 2-connected graphs through several lemmas and theorems: - A graph is 2-connected if it remains connected after removing any single vertex. Equivalently, for any two vertices there exist two internally disjoint paths between them. - Whitney's theorem states that if a graph with at least three vertices is 2-connected, then for any two vertices there exist internally disjoint paths between them. - A characterization theorem establishes that several graph properties are equivalent to a graph being 2-connected, including having internally disjoint paths between all vertex pairs and every pair of edges lying on a common cycle.

Uploaded by

Semy Zambrano
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 9

2-Connected Graphs

Chih-wen Weng
September 22

0-0
2-connected graph

Recall G is 2-connected if κ(G) ≥ 2. Equivalently G is


connected and G − x is connected for any vertex x ∈ V .
Definition 0.1. Let u, v be two vertices in V . Two
u, v-paths are internally disjoint if they have no common
internal vertex.

1
Lemma 0.2. Suppose for any two distinct vertices u, v
there exist internally disjoint u, v-paths in G. Then G is
2-connected.

Proof. Of course G is connected. We shall show G − x is


connected for any x ∈ V . Pick two vertices u, v in G − x
and two internally disjoint u, v-paths. Then at least of
the u, v-paths is in G − x. Hence G − x is connected.
Definition 0.3. For u, v ∈ V (G), let ∂(u, v) be the
length of shortest u, v-path. ∂(u, v) is called the distance
of u, v.

2
Whitney Theorem[1932]
Theorem 0.4. Suppose G is 2-connected with at least
three vertices. Then for any two distinct vertices u, v
there exist internally disjoint u, v paths in G.

Proof. We prove by induction on the distance ∂(u, v).


First suppose ∂(u, v) = 1. Hence uv is an edge. We need
to find another path in G − uv. Recall that
0
κ (G) ≥ κ(G) ≥ 2. Hence G − uv is connected. Next
suppose the theorem is true for ∂(u, v) ≤ k.

3
Continue of Proof

Proof. Now assume ∂(u, v) = k + 1. Pick a vertex w with


∂(u, w) = 1 and ∂(w, v) = k. By induction we can find
two internally disjoint w, v-paths P , Q. Since G − w is
connected we can find a u, v-path R in G − w. Let z be
the first vertex in R that meets P or Q, say P . Then the
combine of u, z-path of R with the z, v-path of P is
internally disjoint from uw ∪ Q.

4
Expanding Lemma
0
Lemma 0.5. Suppose G is 2-connected and G is
obtained from G by adding a new vertex y with at least 2
0
neighbors in G. Then G is 2-connected.
0
Proof. Of course G is connected. We need to show
0 0
G − x is connected for any vertex x in G . Pick two
0
vertices u, v in G − x. If u, v are in G then we can find a
u, v-path in G − x by the 2-connected property of G. So
assume one of u, v is y, say v = y. Choose a neighbor w of
y that is not x. Pick a u, w-path in G − x. Combine this
0
u, w-path with wv to obtain a u, v-path in G − x.

5
Characterization
Theorem 0.6. Let G be a graph with at least three
vertices. Then the following (i)-(iv) are equivalent.
(i) G is 2-connected.
(ii) For all vertices u, v ∈ V , there are internally
disjoint u, v-paths.
(iii) For all vertices u, v ∈ V , there is a cycle through
u and v.
(iv) δ(G) ≥ 1 and every pair of edges in G lies on a
common cycle.

6
Proof

Proof. (iv)⇒(iii) Clear.


(iii)⇒(ii) Clear.
(ii)⇒(i) This Lemma 0.2.
(i)⇒(iv) Since G is connected with at least 2 vertices,
every vertex has degree at least 1. Let uv and xy be two
edges in G. Add to G new vertices w with neighborhood
{u, v} and z with neighborhood {x, y}. Since G is
2-connected, the Expansion Lemma implies the new
0
graph G is 2-connected.

7
Continue of Proof

Proof. By Theorem 0.4, there are two internally disjoint


0
w, z-paths P, Q in G . Note that u, v (resp. x, y) are in
different paths since w (resp. z) has degree 2. Say
u, x ∈ P and v, y ∈ Q. Let C be the cycle combining the
w, z-path P and the z, w-path of reversed Q. Note that
v, w, u and x, z, y are two paths of length 2 in C.
Replacing v, w, u and x, z, y by v, u and x, y respectively
yields the desired cycle through vu and xy.

You might also like