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

Difficulty level: Easy task (using definitions and simple reasoning)
Reasoning task
Cs translation
Send comment on task by email