# Prove G is non-planar by contradiction

$$G=(V,E). |V| = 25; |E| = 50.$$ For every vertex $$v \in V$$, the degree of that vertex $$d(v)=4.$$ I am given that the shortest cycles in $$G$$ are 4-cycles (i.e. with 4 vertices).

For a contradiction I assumed that G is planar. Hence G would have a number of regions/faces $$|R|$$ with boundary lengths $$b(r)$$. From this I got:

$$\begin{equation*} \sum_{r \in R} b(r) = \sum_{v \in V}d(v) = 2|E| = 100, \end{equation*}$$

and by Euler's theorem: $$\begin{equation*} |V| - |E| + |R| = |R| - 25 \geq 2 \implies |R| \geq 27. \end{equation*}$$

So a lower bound on the first summation would be:

$$\begin{equation*} \sum_{r \in R} b(r) \geq 27 b(r)_{min}. \end{equation*}$$

where $$b(r)_{min}$$ is just the length of the smallest boundary for a region. My guess here is to say that $$b(r)_{min}$$ = 4, given the information I made bold at the start. This would give me the $$100 \geq 108$$ contradiction I'm after, but this is just a guess and I don't know why/if this is true. I know that the boundaries in a planar drawing are cycles, and maybe these cycles don't change/get shorter when going from planar to non-planar, but again I'm guessing here. Could someone help me finish this proof and tell me if my intuition is right/wrong? Thanks!

## 1 Answer

Suppose it exist. So each face has at least 4 edges. By double counting between edges and faces we have$$2 |E| \geq 4|F|\implies |E|\geq 2|F|$$ By Euler theorem we have $$|V|-|E|+|F|= 2$$

so $$|E| \geq 2(2+|E|-|V|)$$

and thus $$2|V|-|E|\geq 4 \implies 50-50\geq 4$$ A contradiction.