I'm studying for a final and my textbook often uses the equation $$ e \le 3v-6 $$ (seems to be a theory or corollary) for some of the graph theory proofs, but I can't find anywhere as to where this equation is derived from therefore making it hard for me to attempt to use it as part of a solution.
Could someone please tell me how it's derived and why it's significant?
Much Thanks!
On
For a simple, connected, planar graph with $v \ge 3$ vertices and $e$ edges, $e \le 3 v - 6$. See Wikipedia.
On
This is only applicable to planar graphs, for instance $K_5$ has $5$ vertices but $10 > 15 - 6$ edges. This answer will give you a proof to this common theorem.
On
That's the number of edges in a planar graph with all faces triangles, and thus the highest possible number of edges in a planar graph. \begin{align*}V+F &= E+2\\ V+\frac23 E &= E+2\\ V-2 &= \frac13E\\ 3V-6 &= E\end{align*}
On
Let $G$ be a planar graph and let $F$ denote the number of faces and $E$ denote the number of edges, and $V$ denote the number of vertices. Euler's formula says that $V-E+F=2$ which means $F=2+E-V$. On the other hand, the length of perimeter surrounding a face is at least $3$. So then if we sum up the length of each face, which is twice number of edges, we get: $6+3E-3V=3(2+E-V)=F*3 \leq \sum_{f \in face(G)}{len(f)}=2*E$. which means $E \leq 3V-6$.
This formula is valid specifically for planar graphs. If a graph with $3$ or more vertices is planar, and $e$ is the number of edges and $v$ the number of vertices of that graph, then it is true that $$ e \leq 3v-6 $$