How can I visualize the identity $m\leq3n-6$ (where $m$ is the number of edges, $n$ the number of vertices) for simple connected finite planar graphs?
Visualizing identity $m\le3n-6$ for simple connected finite planar graphs
-
0Your intuition, that it might have visual meaning, is correct. – 2012-04-29
3 Answers
I will use the easier to comprehend $E$ and $V$ in place of $m$ and $n$. You want to show $I = 3V - E \geq 6$. Call $I$ the "invariant" of the graph. The inequality on $I$ is a discrete analogue of the Gauss-Bonnet theorem in differential geometry.
$2I$ is the sum of $(6 - \deg v)$ over all vertices. The lower bound on $I$ means that average degree must be less than $6$ in a (finite) planar graph. Better: the average local curvature must be positive for a graph to be drawn on a sphere.
Some conditions are needed on the graph for this interpretation to hold. The graph must be above a certain size or the inequality is false. If it is empty, $E=V=0$ and the statement is false. If a tree, $V = E+1$ and one needs $E \geq 2$. These cases are degenerate in that the result is about embeddability into surfaces, and if the 1-skeleton of the graph is contractible the problem is not topological in nature. A cycle of length $2$ or more satisfies the inequality so assume that there is a nontrivial cycle. A simple loopless graph is necessary, otherwise one can hold $V$ constant and add an unlimited number of edges. Within noncontractible simple graphs the minimal case is a triangle and the inequality holds in that case. To view $6 - \deg v$ as a combinatorial measure of local curvature of a surface, the minimal cycles in the graph should all be triangles, and as we will see, this is reflected as slack in the inequality on $I$ if some of the faces are not triangular.
$I$ is reduced by adding edges between unconnected vertices (each addition of an edge reduces $I$ by $1$). Thus for a fixed set of vertices $V$ the critical case will be where every face is a triangle, i.e., a triangulation. If the triangulation is of a compact surface then the number of faces $F$ satisfies $2E = 3F$ and the invariant is $I = 3V - 3E + 3F$, which is 3x the Euler characteristic of the surface. We conclude that $I = 3(2-2g) = 6 - 4g$ where $g$ is the genus of the surface, which explains the number $6$ and the assumption of planarity, $g=0$.
So: a visual interpretation of $I$ is, draw the graph on a surface of genus $g $, adding some number $k$ of edges if necessary so as to obtain a triangulation; then $I = 6 - 4g + k$. If the graph is planar then $g=0$ is attainable, with $I = 6+k$, and $I = 6$ if and only if there is a drawing with all faces triangles. The inequality is true for planar simple graphs with $3$ or more vertices, and equality holds precisely for triangulations of a triangle, as proposed in other answer.
Finally, if for each face one defines its excess as $(e - 3)$, the number of edges by which it is larger than a triangle, then $I = 6 - 4g + \text{total excess of the graph}$. This quantity is calculated for any particular drawing of the graph, but $I$ is by definition expressible purely in terms of the number of vertices and edges, so that total excess minus $4g$ is independent of the drawing.
Say you have a graph with $m = 3n - 6$. Then, add one more vertex. This relationship says you can add at most 3 edges to keep the graph planar.
If you want more, work on this yourself. Draw 3 vertices. Draw as many edges as you can to keep the graph planar. The inequality says $m \leq 3 \cdot 3 - 6 = 3$. Of course, you can get up to 3 by drawing all edges and forming a $K_3$.
Now, add one more vertex. Draw as many edges as you can, yet keep the graph planar. There are only 3 possible extra edges and you can actually draw all 3 since a $K_4$ is also planar.
Now, add one more vertex. Draw as many edges as you can, yet keep the graph planar. The inequality says you can draw at most 3. In this case, there are 4 possible edges, so you won't be able to draw them all.
Repeat the process (by continuing on and/or starting over) until it makes a bit more sense.
Start by visualizing three vertices, with three edges - a triangle.
If we add a vertex outside the triangle, we may only be able to draw two more edges (possibly three), but if we instead add the vertex inside the triangle, we will certainly be able to add three edges.
In order to add the maximum number of edges possible, whenever we add a vertex, we must place it inside one of the existing triangles. This results in three additional edges for each additional vertex. Thus the ratio of edges to vertices (in the optimal case) is 3:1, giving us (roughly) $m \leq 3n$. Considering our base case (n=3, m=3), we can see that in fact $m \leq 3n - 6$.
-
0You are right that repeated subdivision of a triangle into triangles saturates the inequality. One would need a separate argument to show that no other saturation (or violation) of the inequality is possible. See other answer for one method. It is possible that every triangulation of a triangle can be done by adding one vertex at a time but this seems more difficult to prove than the lower bound on $3n - m$. – 2012-04-29