4
$\begingroup$

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{ ?}$$

$\endgroup$
  • 10
    $\begingroup$ Hi, not sure to see the point, as you'll probably end up "re-proving" Euler's formula in such a proof. Many many results about planar graphs are (in)direct consequences of Euler's formula. I anticipate that it should be difficult to prove this fact independently of Euler's formula. Waiting to see if someone contradicts me. $\endgroup$ – Thomas Lesgourgues Oct 22 at 8:52
  • 3
    $\begingroup$ The proof that $K_5$ is non planar usually comes directly from Euler's identity... $\endgroup$ – Thomas Lesgourgues Oct 26 at 8:56
  • 2
    $\begingroup$ Tiling the plane with equilateral triangles creates an edge graph all of whose vertices have degree $6$. $\endgroup$ – Christian Blatter Oct 26 at 18:50
  • 2
    $\begingroup$ This is not intended as a serious answer but -- we may assume that the graph is a triangulation, since adding edges only makes it harder. By the circle packing theorem en.wikipedia.org/wiki/Circle_packing_theorem , a triangulation of the sphere can be realized by geodesic triangles. The sum of the angles of a spherical triangle is always $> \pi$, and the sum of the angles around a vertex is always $2 \pi$ so, in a triangulation of a sphere, we always have $2V > F$. By the usual handshake count, $3F = 2E = \sum \deg(v_i)$, so $6V > \sum \deg(v_i)$ and some $\deg(v_i)$ must be $<6$. $\endgroup$ – DES-SupportsMonicaAndTransfolk Oct 28 at 15:24
  • 2
    $\begingroup$ This is not a serious answer because, not only is Euler's formula about a hundred times easier than the circle packing theorem, it is an easy corollary of it. This is like asking "Can I fly into JFK without seeing the Empire State Building?" and answering "Yes, if you close your eyes." $\endgroup$ – DES-SupportsMonicaAndTransfolk Oct 28 at 15:25
8
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ Very interesting answer!! Few small notes : 1. Only for references, regarding embedding with straight lines, this is directly known as Fary's thorem 2. Could you add a clear def of $\tilde{G}$, the subdivided graph, as in the graph adding a vertex at each breakpoint of edges. Also I think we should talk about embeddings, not graphs. the value of $\tilde{f}_j$ and $\tilde{v}_k$ could change with another embedding. 3. When removing one subdivision, it could also reduce one face by 2 (in case of bridges). No impact on calculation $\endgroup$ – Thomas Lesgourgues Nov 5 at 8:08
  • $\begingroup$ 4. You state that $f_2=0$. That's not always true no? the simple example of $K_2$ comes in mind. I don't know if we might encounter other cases (just to be thorough and ensure we don't miss any situtation). $\endgroup$ – Thomas Lesgourgues Nov 5 at 8:10
  • 2
    $\begingroup$ And finally, for the english "We are going to, write at the start, hit an annoying issue", [sic.] :) That's amazing otherwise! $\endgroup$ – Thomas Lesgourgues Nov 5 at 8:12
  • $\begingroup$ Thanks a lot for the proof, it brings me back to high school days and shows a new point of view, amazing! $\endgroup$ – athos Nov 5 at 19:30
0
$\begingroup$

(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.

$\endgroup$
  • 2
    $\begingroup$ I agree with you that start with something like Jordan Curve Theorem it’s likely to prove $K_5$ is nonplanar. However , given a graph $G$ with each vertex has $d\ge 6$, how to prove there’s a subgraph $H$ from $G$ such that $H$ is $K_5$ or an expansion (i.e. subdivision) of $K_5$? My understanding is that Wagner’s theorem or Kuratowski ‘s theorem depend on Euler’s formula. $\endgroup$ – athos Oct 26 at 23:09
  • $\begingroup$ O.k, didn't know that, thanks for info $\endgroup$ – friedvir Oct 26 at 23:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.