Connectivity of planar graphs
Task number: 3973
For which largest \( k \) there exists a planar vertex \( k \)-connected graph?
Solution
Each planar graph has a vertex of degree at most 5. The edge connectivity is bounded by 5 from above and therefore also the vertex connectivity.
If we are looking for a 5-connected planar graph, it must also have minimum degree 5. If we choose, for example, the icosahedron, it can be shown by analyzing three cases (according to the distance of vertices) that 5 vertex disjoint paths lead between every two vertices.
Alternatively, the non-existence of cuts of size 4 can be shown. Since the icosahedron graph is a planar triangulation, each minimal cut (due to inclusion) is also a cycle. This cycle, viewed as the Jordan curve, should separate vertices of the components. An analysis of the cases shows that no such suitable 4-cycle exists.
Answer
The questioned \( k \) is equal to 5, ie there are planar 5-connected graphs, but not 6-connected ones (both edge- and vertex-connected).
