What is the maximum connectivity of a planar graph?

534 Views Asked by At

The Icosahedral Graph is a simple 5-connected planar graph. Is there a 6-connected planar graph?

In general, is there a theoretical maximum on the vertex connectivity of planar graphs? This is spurred since the number of edges is bounded by $3n-6$, and that could set an upper bound on the vertex connectivity.

1

There are 1 best solutions below

0
On BEST ANSWER

I think you pointed at the exact right direction. As the number of edges is at most $3n-6$, there must be a vertex $v$ of degree at most $5$. Delete the neighbors of $v$, and the graph falls apart (unless it had at most 6 vertices).