Hide sidebar
Lê Nguyên Hoang
By Lê Nguyên Hoang
PhD Student in Applied Maths at Polytechnique of Montreal.
Engineer of the Ecole Polytechnique, France. (X2007)

Euler’s Formula and the Utilities Problem

Abstract I was a kid when I was first introduced to the deceptively simple utilities problem. It's only lately that I've discovered its solution! And it's an amazing one! Indeed, it provides a wonderful insight into some fundamental mathematics, including Euler's formula! This is nothing less than the gateway to the wonderful world of algebraic topology! | Outline | Posted: June 20th, 2013 | Last Modified: June 24th, 2014 | Tags: , , , , | Views: 4399 | 1 Comment »

The Utilities Problem

In this article, we’ll present and solve the classical utilities problem, using one of the most beautiful formulas of mathematics, due to Leonhard Euler. This will have us walking a few steps in the stunning world of algebraic topology! But first things first, let’s talk about the utilities problem!

What’s the utilities problem?

Three houses in a small village all need to be supplied with water, gas and electricity. Can you make all the connections between the houses and the supplies without having any two cable crossing?

Hummm… Let me try…

Got it?

No! The last cable always is the problem!

Let me try… Here’s what I got…

The Utilities Problem - Bad Solution

You too have an intersection!

I know! I’m no better than you! But getting rid of this intersection is impossible. That’s what I was told when I was a kid, but it’s always frustrated me not to see why. Fortunately, I’ve recently discovered a proof. And it is beautiful!

Euler’s Formula for Planar Graphs

First, I need to talk to you a little bit about graph theory. Because that’s what we are dealing with here!

What’s graph theory?

Graph theory is the study of connectivity between points called vertices. In our case, houses and supplies can all be modeled by such vertices. Now, our problem is to connect each house with all supplies with lines called edges. And avoiding intersections means that we want our graph to be planar. So, in graph theory terms, the problem consists in finding a planar graph connecting each of three vertices with all three other vertices.

Wait. All you’ve done so far is restating he problem with complicated technical terms, right?

You see right through me! But this will enable me to state the mighty Euler’s formula as it’s usually done!

What’s Euler’s formula?

It says that, for any planar graph, $faces-edges+vertices$ always equals 2. Let’s see on the following figure.

Euler's Formula for Planar Graph

Note that the outside of the graph has to be considered as 1 face for the formula to hold. This might seem arbitrary here, but it will make much more sense when we get to polyhedra…

And this holds for any planar graph?

If the graph is connected, yes!

What do you mean by connected?

I mean that all points should be joined through a sequence of edges. Learn more about connectedness with my article on topology!

Spanning Tree

So Euler’s formula holds for any connected planar graph?

Yes! And we can prove it! Actually, give it a try before I provide my proof!

Humm… What’s your proof?

First, let’s remove all edges. Then, we add edges such that each added edge includes one more vertex to the vertices connected so far. So, for instance, we could consider edges $E_1$, $E_2$, $E_3$, $E_4$ and $E_5$. These 5 edges connect all 6 vertices.

This is the construction of what’s known as a spanning tree, that is, a smallest graph connecting all vertices. Trees play a crucial role in graph theory. If you can, please write about them!

We can easily check that, on this graph, Euler’s formula holds. Indeed, there’s only 1 face, and there are one more vertices than edges. I’m going a bit fast, but take your time to really follow through all I’m saying here. Thus, for the spanning tree, $faces-edges+vertices=2$.

OK, but how do we deduce from this that Euler’s formula holds for all connected planar graphs?

We’ve already done most of the work! All we need now is to notice that, whenever we add an edge, we’re also creating a new face! Try it! Add $E_6$. Then $E_7$. And so on!

Indeed! Each new edge creates a new face!

Thus, by adding the 6 missing edges, we’ve created 6 new faces. Eventually, the quantity $faces-edges+vertices$ gets added the 6 faces, but gets also subtracted the 6 edges. That’s why it remains unchanged: This proves Euler’s formula! To be perfectly rigorous in the general case, we’d need to involve a proof by induction, but I guess you get the idea!

OK, I’m convinced. But how does that relate to the utilities problem?

Hehe…

The Solution to the Utilities Problem

First, using Euler’s formula, we can count the number of faces a solution to the utilities problem must have. Indeed, the solution must be a connected planar graph with 6 vertices. What’s more, there are 3 edges going out of each of the 3 houses. Thus, the solution must have 9 edges. Now, since $faces-edges+vertices=2$, we thus have…

$faces = 2+edges-vertices= 2+9-6=5$, right?

Yes! Because of Euler’s formula, a solution to the utilities problem has necessarily 5 faces!

OK… So what?

Now, we’ll show that this is incompatible with the structure of the graph of the utilities problem! And the key is to remark that all faces we create in the utilities problem have at least 4 sides!

Really?

The Utilities Problem

Yes! In fact, you should spend some time finding out why on your own!

Humm…

In other words, there can’t be any triangle!

Humm…

Got it? Try a proof by contradiction: Assume that there is a triangle and show why that can’t be!

OK. So, if there’s a triangle…

Then it has 3 vertices, right? Now, of what kind are the 3 vertices? Can they all be houses?

Obviously not, since there are no edge between houses!

Exactly. Similarly, they can’t all be supplies. More interestingly, 2 of the 3 vertices can’t be of the same kind, since, as you said, there can’t be edges between two vertices of the same kind. So we have 3 vertices all of which have to be of a different kinds. But there are only 2 kinds of vertices. That’s where we get a contradiction.

Graph with 5 Quadrilaterals and 10 Edges

So, no triangle?

No. Now, what’s interesting is the consequence on the number of edges! How many edges are required to make 5 faces, all having at least 4 sides?

20 edges, right?

Are you sure? Can’t edges be used several times?

Yes! In fact, each edge is used for exactly 2 faces, isn’t it?

Yes! Thus, at least 10 edges are required to make 5 faces of 4 sides. On the right is an example of a graph with 5 faces of 4 sides and exactly 10 edges.

But we only have 9 edges in the utilities problem!

Bingo! We have a contradiction! To satisfy Euler’s formula, a solution must have at least 5 faces with at least 4 sides, which means that it has at least 10 edges. Yet, it also needs to have 9 edges, as required by the statement of the problem! Thus, such a solution does not exist!

We’re sooo close to characterizing planar graphs! The graph of the utilities problem is called $K_{3,3}$. Another similar reasoning based on Euler’s formula would also show that interconnecting all of 5 computers can’t be done without intersection (do it!). Mathematically, we say that $K_5$ isn’t planar. Now, the important result of characterization of planar graphs is the following theorem: planar graphs are graphs which don’t have $K_{3,3}$ nor $K_5$ as minors. It’d be a bit long to define what minors are here, but if you can, you should write about this!

To recapitulate, check this explanation by the great James Grime on SingingBanana:

James Grime seems to relate that to polyhedra in a way I’m not sure I understand…

Hehe… That’s because Euler’s formula was actually addressed to polyhedra rather than planar graphs. In fact, graph theory didn’t exist at that time! But the link between planar graphs and polyhedra with no holes is one of these extremely powerful connections in mathematics! This encounter was very fecund, as it gave birth to algebraic topology! Let’s explore it!

Euler’s Formula for Polyhedra

In short, Euler’s formula still holds for polyhedra with no holes. For instance, the cube has 6 faces, 12 edges and 8 vertices. Thus, $faces-edges+vertices=6-12+8=2$. It satisfies Euler’s formula!

So where does this connection come from?

In two words, from the stereographic projection. This stereographic projection is beautifully explained in this extract from the series A Walk through Mathematics made by researchers and artists at ENS Lyon in France:

I really don’t see the connection between the stereographic projection and what we’ve talked about so far…

Let’ take a polyhedron with no hole. We can sort of blow it up to make it sphere-like. Then, let’s embed it inside a sphere and project it, by putting a lamp inside and observing the shadows drawn by the edges of the polyhedron on the sphere. This is what’s done in the following figure with quadrilateral-based pyramid:

Polyhedron projected on Sphere

Notice that if the polyhedron is convex (which means that it was indeed blown-up), then projected edges on the sphere should not intersect.

This idea of blowing up objects is in fact at the heart of Perelman’s recent proof of Poincaré conjecture. Sort of…
OK… What now?

Now we use the stereographic projection! We can always turn a bit the sphere such that its North pole doesn’t match a vertex of the polyhedron nor an edge. Then, we’ll have a one-to-one match between the vertices and edges on the sphere with their stereographic projections on the plane. This is what’s done below:

From Projected Polyhedron to Planar Graph

The image obtained on the plane is then a graph. Now, if two edges of this graph intersects, then the intersection is the projection of an intersection of the two edges on the sphere. But, as we said, at least for convex polyhedra, there’s no such intersection for the polyhedron projected on the sphere. Thus, the graph projected on the plane is…

A connected planar graph!

Bingo! And Euler’s formula holds for connected planar graphs. Now, there’s a one-to-one match between vertices, edges and faces of the initial polyhedron and the projected graph. Thus, Euler’s formula still holds for the original polyhedron with no hole! We have proved Euler’s formula!

Woohoo! Wait… Is there a one-to-one match of faces too?

Yes! You can check it out on your own. In particular, the front face of the pyramid that we see is mapped to…

The exterior face of the planar graph! Waw! That’s awesome!

I know!!! Euler’s formula has plenty of other beautiful proofs. Another brilliant one is given in this lecture by N.J. Wildberger. It’s worth checking it out!

Euler Characteristic

I’m not sure where it is that we needed the polyhedron not to have any hole…

Some polyhedra cannot be blown-up into a sphere-like polyhedron! This is the case where they have holes. Below are two such examples. The first one is the famous Szilassi polyhedron. It also has the surprising property of having all of its 7 hexagonal faces all touching one another! Its discovery, made as late as 1977, was a shock in the mathematician community!

Holed Polyhedra

The surprises of these new objects have put forward the importance of the concept of holes in mathematics, and, in particular, in topology. A great example is the recent of proof of Poincaré conjecture by Perelman. And the Euler characteristic plays a key role in the understanding of these holes.

What’s the Euler characteristic you’re mentioning?

Haven’t you guessed? The Euler characteristic is the quantity we have been studying so far, that is, $\chi = faces-edges+vertices$. I don’t know why, but it’s commonly denoted with this greek later $\chi$.

So if there’s no hole, Euler’s formula says that $\chi=2$?

Yes!

But if there’s a hole, do we have $\chi=0$ like in the examples above?

Humm… Let me ask you a question. What’s a hole? Can you provide a clear definition of a what a hole is?

Humm… I’ve read something about homeomorphisms, even though I’m not sure what that means!

Haha! You can find it out with my article on Poincaré conjecture! Another cool definition of holes is based on the idea of cuts, as explained in this talk by Jason Ross.

Cut in Holed Polyhedron

More formally, the number of holes, known as genus, is the maximum number of non-intersecting cuts along closed loops on the surface without disconnecting the object. This genus is usually defined for closed surfaces like the sphere or the torus, but it can also be defined for polyhedra. Both of the holed polyhedra I showed earlier have a genus equal to 1. The figure on the right illustrates a cut that can be done, along the drawn red loop.

So, now, can we say that polyhedra with genus 1 have Euler characteristic 0?

We can say even more! If we denote $g$ the genus, then we have the following beautiful formula relating the genus to the Euler characteristic: $\chi = 2-2g$.

Arg… I should have guessed that!

This formula is essential in algebraic topology for the classification of orientable closed surfaces.

What’s an orientable closed surface?

The awesome question is rather: What’s a non-orientable surface? I’m dying to answer this question right now, but, for clarity, it’ll have to wait for a future article…

Now, closed surfaces are surfaces which are limited in space and have no boundary. Typically, this is the case of the sphere and the torus. Now, in fact, all closed surfaces which can be represented in our 3D world are orientable. So, don’t worry to much about orientability here.

So what’s the classification you mentioned?

Easy! First, it says that all orientable closed surfaces with genus 0 are continuous deformations of a sphere. For instance, a cube has genus 0, thus the cube can be deformed continuously into a sphere. We say that the cube is homeomorphic to the sphere. For a proper definition of homeomorphism, read my article on Poincaré conjecture.

OK… What about orientable closed surfaces with another genus?

Well, all orientable closed surfaces with genus 1 are homeomorphic to the torus. In particular, the two holed polyhedra above can be deformed continuously into tori. The following figure displays the deformation of the second holed polyhedron into a torus:

Deformation into Torus

This construction is in fact what proves that the Euler characteristic of a torus is 0. Indeed, on the torus I drew above, we can retrieve the 9 faces, 18 edges and 9 vertices of the initial polyhedron!

8-Holed Torus

What about orientable close surfaces of higher genus?

In the general case, an orientable close surface of genus $n$ will be homeomorphic to an $n$-holed torus. On the right is an example of an 8-holed torus.

The Utilities Problem on a Torus

Let’s get to what James Grime mentioned about the utility problems on a torus!

Yes!

When we proved the non-existence of planar graphs, we actually used the fact that planar graphs have an Euler characteristic $\chi=2$ to deduce $faces=5$. But if we now consider graphs on a torus, then $\chi=0$, thus, $faces=3$. Thus, on a torus, we might no longer have any contradiction!

Well, according to James Grime’s video, there even is a solution!

Indeed there is! Why don’t you spend some time searching for it?

Humm…

To help you, keep in mind that a torus is like the map of PACMAN: It’s a rectangle such that, when you go out of the rectangle towards the right, you appear at the same height but on the left. Similarly, if you go up, then you reappear at the bottom with the same left-right position. I talk more about this in my article on Poincaré conjecture.

That helps!

Did you find a solution?

I did!

Great! Below is my solution to the utilities problem on a torus.

The Utilities Problem on a Torus

I’ve numbered the faces. The sides connect the four extreme areas, making up the face $F_1$. As you can see, as Euler’s formula predicted it, there are 3 faces.

And we do have $faces-edges+vertices=0$!

Great reflex! Indeed, this graph has an Euler characteristic equal to 0. Now, let’s analyze the faces in more details. Faces $F_2$ and $F_3$ are quadrilaterals. Regarding $F_1$, all edges except the one bringing water to the blue house are its boundaries. It thus has 8 sides. This all makes up a total of 4+4+8=16 sides, which require 8 edges to be done. But we have 9 edges. Why?

Hum…

Any idea?

Tricky one…

Let’s move vertices and edges to have a clearer view at the graph! Note that there is only one edge connecting faces $F_2$ and $F_3$, so I’ve placed it in the middle. Then, I can reposition the houses and supplies so that $F_2$ and $F_3$ now form squares. This gives the figure on the left below. I can now even plot the graph on an actual torus, as done on the right!

The Utilities Problem on a Torus 2

Do you better see what happens?

Yes! The purple and orange edges which go out of the rectangle actually separate $F_1$ with itself!

Yes! As a result, these two edges are sort of used to cut the torus to make it an actual face with no hole. And they thus appear twice as sides of the face $F_1$. This face thus actually has 10 sides! To better see it, let’s draw it!

Face F1

As you can see the bold horizontal and vertical edges appear twice in $F_1$. If you’re familiar with algebraic topology, this figure should definitely ring a bell. If you’re not, wait for my future article on fundamental polygons. In the meantime, you should check Wikipedia’s article or follow Wildberger’s awesome course on algebraic topology!

Let’s Sum Up

We’ve been doing algebraic topology! How exciting is that?

It’s pretty cool!

Because closed surfaces are strongly related to homeomorphic polyhedra, the study of polyhedra has turned out to be essential to the understanding of topology and connectedness, which is studied by algebraic topology. And Euler’s formula thus plays a key role in this field. In fact, Euler characteristic can easily be generalized to higher dimensions. After all, it more or less adds the number of subelements of polyhedra of all dimensions, with a negative sign before odd dimensions. Better insights are given by homology… But that’s going to be for another article!

If you can, please write an article on homology, homotopy or any of the numerous cool stuffs algebraic topology has to offer!

To finish, let me draw a strong connection between all we’ve discussed and the mythic 4 color theorem. I mention this theorem in this extract from my talk A Trek through 20th Century Mathematics.

I do understand much better why the 4-color theorem holds on a sphere but not on a torus!

Hehe. In fact, I’ve introduced in this article the object which immediately proves that you may need at least 7 colors to color a map on a torus! Can you find it?

I guess I should use your holed polyhedron, shouldn’t I?

No. Not my holed polyhedron…

Oh yeah! You mentioned that Szilassi polyhedron had 7 hexagonal faces all connected…

Yes! Thus, all faces must have a different color than all others. This means that 7 colors are required to color Szilassi polyhedron! The not-4-color theorem on the torus sounds less troubling now, doesn’t it? Now, we still need to prove that 7 colors are sufficient, but I’ll let you work on that.

And when you get it all, share what you’ve learned on Science4All!

Finally, I’ve put a video of a talk by William Dunham on Euler in the references. Check it out! It’s absolutely amazing!


Subscribe to Science4All to stay in touch with awesome science:

Food for Thoughts

  • Prove that a graph of 5 all-connected computers isn't planar.The indications are given in the article!
  • Prove that the 4 color theorem is true on a sphere if and only if it holds on a plane.Use stereographic projection!
  • Does the 4 color theorem hold for infinite planar graphs?If, in any bounded region, the infinite planar graph is actually finite, then yes. Otherwise...

Contributors

  • No one so far... So you can be the first to contribute to this article!

Goingfurther Articles

  • Poincaré Conjecture and HomotopyLê Nguyên Hoang Poincaré Conjecture and Homotopy
    By Lê Nguyên Hoang | Updated:2014-04 | Views: 3778
    Poincaré conjecture is the most recent major proven theorem. Posited a century ago by Henri Poincaré, this major conjecture of topology was solved by Gregori Perelman. It has revolutionized our understanding of space and raised intriguing questions regarding the global structure of our Universe.
  • The Tortuous Geometry of the Flat TorusLê Nguyên Hoang The Tortuous Geometry of the Flat Torus
    By Lê Nguyên Hoang | Updated:2014-06 | Views: 5817
    Take a square sheet of paper. Can you glue opposite sides without ever folding the paper? This is a conundrum that many of the greatest modern mathematicians, like Gauss, Riemann, and Mandelbrot, couldn't figure out. While John Nash did answer yes, he couldn't say how. After 160 years of research, Vincent Borrelli and his collaborators have finally provided a revolutionary and breathtaking example of a bending of a square sheet of paper! And it is spectacularly beautiful!
  • The Cubic Ball of the 2014 FIFA World CupLê Nguyên Hoang The Cubic Ball of the 2014 FIFA World Cup
    By Lê Nguyên Hoang | Updated:2014-07 | Views: 2134
    I know this sounds crazy. Even stupid. But Adidas did design a cubic ball, called brazuca, for the 2014 World Cup. And, yet, this cubic ball is rounder than any previous ball in football History. How is it possible? This article explains it.

Related Articles

  • Topology: from the Basics to ConnectednessLê Nguyên Hoang Topology: from the Basics to Connectedness
    By Lê Nguyên Hoang | Updated:2014-03 | Views: 2325
    Topology was my favorite course in pure maths. I love it because it's a powerful abstract theory to describe intuitive and visual ideas about space. This article gives you an introduction to this amazing field. We'll introduce graph topology, metric spaces, continuity and connectedness.
  • Proof by Mathematical InductionLê Nguyên Hoang Proof by Mathematical Induction
    By Lê Nguyên Hoang | Updated:2014-04 | Views: 3509
    This article explores the potency of proofs by induction with 4 different stunning puzzles, from a lock puzzle and a lion issue, to the monk problem and the pencil conundrum!
  • Marriage Assignment Problem and VariantsLê Nguyên Hoang Marriage Assignment Problem and Variants
    By Lê Nguyên Hoang | Updated:2014-01 | Views: 2602
    Marriage problems consist in matching boys and girls. They are a very interesting class of problems that include assignment problems, which have a very large range of applications. Additional results have been found for variants which include the introduction of boys and girls' preferences, and cases where people cannot be categorized into two groups.
  • Non-Euclidean Geometry and Map-MakingScott McKinney Non-Euclidean Geometry and Map-Making
    By Scott McKinney | Updated:2013-01 | Views: 1535
    Geometry literally means "the measurement of the Earth", and more generally means the study of measurements of different kinds of space. Geometry on a flat surface, and geometry on the surface of a sphere, for example, are fundamentally different. A consequence of this disparity is the fact that it is impossible to create a perfectly accurate (flat) map of the Earth's (spherical) surface. Every map of the Earth necessarily has distortions. In this post we look at a few different methods of map-making and evaluate their distortions as well as their respective advantages.

 

One Comment on “Euler’s Formula and the Utilities Problem”

  1. 1 Ex-plane something to me… | Mathelogical Mayhem said at 9:06 pm on April 27th, 2014:

    [...] http://www.science4all.org/le-nguyen-hoang/eulers-formula-and-the-utilities-problem/ Share this:TwitterFacebookGoogleLike this:Like Loading… [...]

You must log in to comment this article.