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 |
---|---|
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 |