Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Your intuition, that it might have visual meaning, is correct. –  zyx Apr 29 '12 at 2:07
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
    
If we have 3 vertices and add a vertex outside the triangle, we can still draw all 3 edges. It is not at all necessary to add it inside a triangle. But, adding it inside a triangle shows that we can always add 3 more edges. –  Graphth Apr 28 '12 at 19:23
    
Yes, it is possible, but not in all cases. I will edit my answer, thanks. –  Andrew Parker Apr 28 '12 at 19:25
    
Dear Andrew, thanks for your answer. But, I still think it's a bit off. I think your answer is showing that we can always add 3 at least 3 edges. So, you are showing that there is always a graph with $m \geq 3n - 6$. The question is asking about $m \leq 3n - 6$. Does that make sense? If we combine the two, of course, it says that for any $n$, there is always a graph with $m = 3n-6$. But, again, the question is about $\leq$. –  Graphth Apr 28 '12 at 19:34
    
No, we clearly cannot draw more than three edges with my solution. If you place the new vertex within a triangle, you certainly cannot draw any edges to vertices outside the triangle without violating the 'planar-ness' of the graph. –  Andrew Parker Apr 28 '12 at 19:37
    
And indeed, the question is (somewhat) about $\leq$, which means establishing a maximum value. It just so happens that for any $n$, we can achieve the maximum. My response is about how to visualize this maximum (which was the real question). –  Andrew Parker Apr 28 '12 at 19:42
show 5 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.