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.
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\}$.