Thomassen’s theorem on -connected graphs
Every -connected (http://planetmath.org/KConnectedGraph) graph with more than 4 vertices has an edge such that (http://planetmath.org/EdgeContraction) is also -connected.
Note: denotes the graph obtained from by contracting the edge . If we also use the notation .
Suppose such an edge doesn’t exist. Then, for every edge , the graph isn’t -connected and can be made disconnected by removing 2 vertices. Since , our contracted vertex has to be one of these two. So for every edge , has a vertex such that separates . Any 2 vertices separated by in are separated in by . Since the minimal size of a separating set is 3, every vertex in has an adjacent vertex in every component of .
Now we choose the edge , the vertex and the component such that is minimal. We also choose a vertex adjacent to in .
By construction is not -connected since removing disconnects from . So there is a vertex such that separates and as above every vertex in has an adjacent vertex in every component of . We now consider a component of that doesn’t contain or . Such a component exists since and belong to the same component and isn’t connected. Any vertex adjacent to in is also an element of since is an element of . This means is a proper subset of which contradicts our assumption that was minimal.
|Title||Thomassen’s theorem on -connected graphs|
|Date of creation||2013-03-22 13:11:09|
|Last modified on||2013-03-22 13:11:09|
|Last modified by||Mathprof (13753)|