1. E ≤ 3V
Let G be a simple planar graph with V vertices and E edges. It follows from Euler’s theorem that
E ≤ 3V
In fact, we have (when V is at least 3,) that E ≤ 3V – 6.
To see this, denote by F the number of regions or faces determined by G (in other words, the number of connected components in the complement of the embedded graph). Euler’s theorem asserts that
E – V + F = 2
V – E + F = 2
and now note that every face must have at least three edges and every edge is contained in two faces and therefore , so 6=3V – 3E + 3F ≤ 3V – 3E +2E.
2. F ≤ 4E
Now let K be a two-dimensional simplicial complex and suppose that K can be embedded in . Denote by E the number of edges of K and by F the number of 2-faces of K.
Here is a really great conjecture:
F ≤ 4E
A weaker version which is also widely open and very interesting is:
For some absolute constant C,
F ≤ C E
Remarks: The conjecture extends to higher dimensions. If K is an r-dimensional simplicial complex that can be embedded into then the conjecture is that
Where is a constant depending on r. Here is the number of i-dimensional faces of K. A stronger statement is that . The conjecture also extends to polyhedral complexes and more general form of complexes. In the conjecture ’embed’ refers to a topological embedding.