2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ A planar graph must have a vertex of degree less than six. $\endgroup$ – Gerry Myerson Dec 4 '18 at 22:57
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.