3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Peter Oct 8 '14 at 10:35
2
$\begingroup$

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

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