Return to Answer

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

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

Proposition: If $\Gamma(E,V)$, is a planar graph (no multigraph) then $|E| \ge 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 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.

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$. I wish I could add a graph but I do not have that right (yet). 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.

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

Proposition: If $\Gamma(E,V)$, is a planar graph (no multigraph) then $|E| \ge 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 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.

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 cuadrilateral. 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$. I wish I could add a graph but I do not have that right (yet). 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.

Proposition: If $\Gamma(E,V)$, is a planar graph (no multigraph) then $|E| \ge 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 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.

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$. I wish I could add a graph but I do not have that right (yet). 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.