Thomassen’s theorem on 3-connected graphs

Every 3-connectedPlanetmathPlanetmath ( graph G with more than 4 vertices has an edge e such that G/e ( is also 3-connected.

Note: G/e denotes the graph obtained from G by contracting the edge e. If e=xy we also use the notation G/xy.

Suppose such an edge doesn’t exist. Then, for every edge e=xy, the graph G/e isn’t 3-connected and can be made disconnected by removing 2 vertices. Since κ(G)3, our contracted vertex vxy has to be one of these two. So for every edge e, G has a vertex zx,y such that {vxy,z} separates G/e. Any 2 vertices separated by {vxy,z} in G/e are separated in G by S:={x,y,z}. Since the minimalPlanetmathPlanetmath size of a separating set is 3, every vertex in S has an adjacent vertex in every component of G-S.

Now we choose the edge e, the vertex z and the component C such that |C| is minimal. We also choose a vertex v adjacent to z in C.

By construction G/zv is not 3-connected since removing xy disconnects C-v from G/zv. So there is a vertex w such that {z,v,w} separates G and as above every vertex in {z,v,w} has an adjacent vertex in every component of G-{z,v,w}. We now consider a component D of G-{z,v,w} that doesn’t contain x or y. Such a component exists since x and y belong to the same component and G-{z,v,w} isn’t connected. Any vertex adjacent to v in D is also an element of C since v is an element of C. This means D is a proper subsetMathworldPlanetmathPlanetmath of C which contradicts our assumptionPlanetmathPlanetmath that |C| was minimal.

Title Thomassen’s theorem on 3-connected graphs
Canonical name ThomassensTheoremOn3connectedGraphs
Date of creation 2013-03-22 13:11:09
Last modified on 2013-03-22 13:11:09
Owner Mathprof (13753)
Last modified by Mathprof (13753)
Numerical id 6
Author Mathprof (13753)
Entry type Theorem
Classification msc 05C40
Related topic EdgeContraction