# Planar graphs and connectivity

How many edges must a planar graph with $n$ nodes have that it is sure that it is

a) connected

b) biconnected

c) triconnected

In particular, are all planar graphs with $n$ nodes and $3n-6$ edges ($n\ge 4$) triconnected ?

I tried to use Euler's formula, but it only holds for connected planar graphs. And in the case, that the graph is connected, but not biconnected, the faces need not be bounded by a cycle. How can I deal with this case ?

Since a planar graph with $n$ nodes and $3n-9$ edges ($n\ge 4$) need not be connected (see comment below), at least $3n-8$ edges are required.

• A planar graph with $n$ nodes and $3n-9$ edges ($n\ge 4$) need not be connected : Add an isolated vertex to a maximal planar graph with $n-1$ nodes. So, no number of edges can make sure that the graph is $4$-connected. – Peter Oct 8 '14 at 10:35

Hint for the connected case: if $f(k)$ is the largest possible number of edges for a planar graph with $k$ nodes, then for any positive integers $j$ and $k$ there is a disconnected planar graph with $j+k$ nodes and $f(j)+f(k)$ edges. So to conclude a graph with $n$ nodes and $e$ edges is connected, we need $e > \max \{f(j) + f(n-j) \mid j = 1 \ldots n-1\}$.