Prove planar graph has vertex of degree $\le 5$ without using Euler's formula

Question

As title, it's known that

If $G$ is planar then $G$ has a vertex of degree $\le 5$.

Can we prove this without using Euler's formular

$$v+f-e=2 \text{ ?}$$

Answer 1

I think I have a non-joke answer. Embed our graph in the plane. We are going to, write at the start, hit an annoying issue. I'd like to say that our graph can be embedded such that the edges are line segments. This is true -- see Choi, "On straight line representations of random planar graphs", 1992 -- but I am trying to avoid using results that are stronger than Euler. So, to avoid this, represent edges by piecewise linear paths. Let $G$ be the original graph and $\tilde{G}$ the subdivided graph.

Let $v_k$ be the number of vertices of $G$ of degree $k$ and let $f_j$ be the number of faces of size $j$, including the exterior face. Let $\tilde{v}_k$ and $\tilde{f}_j$ be the corresponding numbers for $\tilde{G}$.

Every edge separates two faces and joins two vertices, so we have $$2 E = \sum_j j f_j = \sum_k k v_k \qquad (\ast).$$

Now, add up all the angles in our graph in two ways. The sum of the angles around each vertex is $2 \pi$, meaning that the sum of all angles is $2 \pi \sum \tilde{v}_k$. On the other hand, the sum of the angles of a $j$-gon is $\pi (j-2)$. This almost means that the sum of all the angles is $\pi \sum_j (j-2) \tilde{f}_j$. However, the external face must be treated separately. Let the external face have $j$ sides. Our sum includes the exterior angles of this face, so the sum of those angles is $2 \pi j - (j-2) \pi = (j-2) \pi + 4 \pi$. So the actual sum of all angles is $\pi \sum_j (j-2) \tilde{f}_j + 4 \pi$. Setting the two quantities equal, and dividing out $\pi$, we obtain: $$\sum_j (j-2)\tilde{f}_j + 4 = 2 \sum_k \tilde{v}_k. \qquad (\clubsuit).$$

We'd like to remove the tilde's from equation $(\clubsuit)$. To this end, consider undoing one subdivision. This reduces the number of edges in two faces by $1$ each, hence decreasing the LHS by $2$, and also removes one vertex (of degree $2$) hence decreasing the RHS by $2$. So we also have $$\sum_j (j-2) f_j + 4 = 2 \sum_k v_k. \qquad (\dagger).$$

Now, since we are dealing with a simple graph, $f_1 = f_2=0$. And, for $j \geq 3$, we have $j \leq 3(j-2)$. So $(\dagger)$ implies $$\sum_j j f_j + 12 \leq 6 \sum_k v_k.$$ Then $(\ast)$ gives $$\sum_k k v_k + 12 \leq 6 \sum_k v_k.$$ So $$\frac{\sum_k k v_k}{\sum v_k} < 6$$ and some vertex has degree less than $6$.

---

Once again though, if you've gone this far, you are very close to proving Euler. We noted already: $$2 E = \sum j f_j = \sum k v_k \qquad (\ast)$$ and $$\sum (j-2) f_j + 4 = 2 \sum v_k. \qquad (\dagger)$$ Rewrite the latter as $$\sum j f_j - 2 \sum f_j + 4 = 2 \sum v_k$$ or, in other words $$\sum j f_j - 2 F + 4 = 2V. \qquad (!)$$ Then combine $(\ast)$ and $(!)$ to deduce $$V+F-E = 2.$$

I guess another way of phrasing this response is that the OP wants a simple geometric intuition, but I view Euler's formula as already having a simple geometric intuition about the sum of angles of a planar $j$-gon. (Thanks to the OP for making me think enough to realize I can understand this with high school planar geometry, though; I've always thought about it using spherical geometry in the past.)

Answer 2

(not sure how much the Wagner's theorem depends on Euler's formula, but if no it would works)

a (kind of a) proof that $K_5$ isn't planar: let us look at $G = k_4$ (with $a,b,c,d\in V$), in one of its plane drawing. therefor, every 3 vertices are a closed shape with no intersections, and there is a $4\choose 3$$=$4 partitions of the plane according to those shapes.(one is the outer side of the graph in the plane).

lets try to create a $G'=K_5$ from it: let $e \in V'$ be the new vertex, and try to put it the plane. each point on the plane is in one of those closed shape, without loss of generality will call it $abc$, and so we could put $e$ it there and put edges, but then the edge $\{d,e\}$ intersect with another edge. $abc$ are arbitrary so we can't create a planar $K_5$. if $G$ wasn't $K_4$ at the start then even if the new edges not intersects then previous ones are and the graph isn't planar.

proof to your claim: assume by contradiction that $G$ is planar and and all of its vertices has degree $>=$ 5. then there is a sub-graph of G that isn't planar ($K_5$), so $G$ isn't planar (according to WAgner's theorem). so the claim stands.