4
$\begingroup$

What is the maximum number of edges a planar subgraph of $K_n$ can have? Is there a simple way to calculate this if not, are there some values of n for which this is easier to find out?

$\endgroup$
  • 4
    $\begingroup$ This must be well-known: The maximum is $3(n-2)$ for every $n>2$ (the maxima of $0,0,1$ for $n=0,1,2$ are clear). The upper bound follows from Euler's relation $V-E+F=2$ upon setting $V=n$ and using the inequality $E \geq \frac32 F$. This inequality is sharp iff every face is a triangle. So to $E=3n-6$ can be attained inductively: start from a triangle for $n=3$, and then to get from $n$ to $n+1$ put a new vertex in some triangle and connect it to the triangle's three vertices to split the original triangle into three. $\endgroup$ – Noam D. Elkies Mar 10 '13 at 1:33
  • 3
    $\begingroup$ Yes it is well known, for example it is on the Wikipedia page Planar graph; voted to close. $\endgroup$ – user9072 Mar 10 '13 at 1:38
  • $\begingroup$ Oh, ok sorry guys. But just to clarify I never found it on wikipedia. SO then the answer is 3(n-2)??? $\endgroup$ – Jorge Fernández Mar 10 '13 at 1:50
  • $\begingroup$ No problem. Yes for n >= 3, it is 3(n-2); see in particular the subsections "maximal planar graphs" and "Eulers's formula" of the above mentioned page. $\endgroup$ – user9072 Mar 10 '13 at 1:57
  • $\begingroup$ Since there is now also an answer in the techncial sense, we can also leave it open from my point of view (I already voted, but have no strong feelings regarding this). $\endgroup$ – user9072 Mar 10 '13 at 2:01
9
$\begingroup$

Suppose the graph has $n$ vertices, $m$ edges, and $f$ faces. By Euler's formula we know that $$n - m + f = 2$$ Now presume there are at least three vertices. Every face must be a triangle, otherwise you can increase the number of edges by dividing a face with an edge. Since every edge borders two faces, $2m=3f$. Therefore $$n - m + \frac{2}{3}m = n - \frac{1}{3}m=2$$ or $$m = 3n-6$$

This can be achieved by triangulating the inside and outside of an $n$-gon. There are $n$ edges that make the $n$-gon, $n-3$ that triangulate the inside, and $n-3$ that triangulate the outside.

Please delete. I didn't see Professor Elkies comment.

$\endgroup$
  • $\begingroup$ you mean delete the question or your answer? $\endgroup$ – Jorge Fernández Mar 10 '13 at 2:06
  • $\begingroup$ I am sure Yosef meant the answer; but I do not it should be deleted. $\endgroup$ – user9072 Mar 10 '13 at 2:20
  • $\begingroup$ "Every face must be a triangle" - this is not true for the outer face. $\endgroup$ – Erel Segal-Halevi Aug 24 '17 at 9:05
3
$\begingroup$

Proposition: If $\Gamma(E,V)$, is a planar graph (no multigraph) then $|E| \le 3 |V| - 6$.

Proof: Let us note that this does not work for a multigraph where more than one edge could be attached to the same two vertices. Imagine a figure (below) of two vertices and 5 segments attached to the two vertices with no intersections other that the ends of the segments. This figure has $|E|=5$ and $|V|=2$, while the inequality $5 \le 0$ is false. A multigraph where $|E| \ge 3 | V | - 6$. Here $5 > 0$.}

Of course $K_n$ is not a multigraph but it is good to be aware of counter-examples.

We first assume that the faces are all triangles and show the inequality \begin{equation} 2|E| \ge 3|F| \quad \quad (1) \end{equation} For example for one face $|E|=3$ and $F=2$ so the equality $6=6$ is achieved. However for two faces (for example a rectangle with a diagonal) we have $|E|=5$ and $|F|=3$, here the inequality $10 > 9$ is strict. We do this by induction over $|F|$ . Let us introduce a new face $|F|$ by adding one more vertex and two more edges on the boundary of the graph (note that since all faces are triangular we can not add faces inside the graph). We need to show that $2| |E| +2| \ge 3| |F|+1|$. \begin{equation} 2 | |E| + 2| = 2 | E| + 4 \ge 3|F| + 4 \ge 3|F| + 3 \ge 3| |F|+1|. \end{equation}

Now we use Eulers equation $|V|-|E|+|F|=2$, from which $|F|=2+|E|-|V|$ and replacing $|F|$ in equation (1) \begin{equation} 2|E| \ge 3 (2 + |E| - |V|) \end{equation} then \begin{equation} |E| \le 3|V| - 6. \end{equation}

Now what happens if a face is not a triangle. We need to add edges until making it a triangle, use equation $|E'| \le 3|V'| -6$ which is valid for triangles then remove the edges and find that for the new graph $|E| \le 3|V| - 6$ is a valid inequality. After adding edges to make all faces triangles we have $|E'| \le 3|V'| -6$ where $|E'|$ and $|V'|$ are the number of edges and vertices of the new triangulated graph. When we remove one edge which is common to two triangular faces, we end up with a quadrilateral. The graph has one less edge without removing any vertex. In general, we remove edges but no vertices to go from the triangulated to the original graph, so $|E| < |E'|$ and $|V|= |V'|$. That is, \begin{equation} |E| < |E'| \le 3 | V'| - 6 = 3 |V| - 6, \end{equation} from which the proposition is shown.

Now, a $K_n$ graph has $n$ vertices so, $|E| \le 3n - 6$. However the number of edges of $K_n$ can be exactly counted. Put the vertices in a unit circle equally spaced. That is, on the $n$ complex roots of the equation $z^n -1 = 0$. Each vertex can visit exactly $n-1$ other vertices, for a total of $n(n-1)$. But each edge was counted twice (from $v_i$ to $v_j$ and from $v_j$ to $v_i$) so the exact maximum is $n(n-1)/2$.

It is interesting that this serves to show the inequality $3n-6 \le n(n-1)/2$. . Use gnuplot or any graph tool to illustrate this. Of course the only solution is for $n=3$, where we have a single triangle. After that the inequality is strict.

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