# F ≤ 4E

## 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 $2E \ge 3F$, 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 $R^4$. 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:

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 $R^{2r}$ then the conjecture is that

$f_r(K) \le C_rf_{r-1}(K),$

Where $C_r$ is a constant depending on r.  Here $f_i(K)$ is the number of i-dimensional faces of K. A stronger statement is that $C_r= r+2$. The conjecture also extends to polyhedral complexes and more general form of complexes. In the conjecture ‘embed’ refers to a topological embedding.