The Theorem that Everyone Else Missed – A Short Proof Of Euler’s Formula

Euler’s Characteristic Formula V-E+F = 2

How is it that for thousands of years the best minds in mathematics did not see the fundamental relationship that, in any regular polyhedron, the sum of the vertices and faces minus the edges equals two? Although this question is interesting, no attempt will be made to answer it. Yet the question, merely by being asked, serves to highlight the tremendous stature of Leonard Euler.

Euler worked from first principles, digging into a topic by performing calculations to get a feel for the shape and edges of a problem, then developed conjectures and proofs based on such research. And so, Euler must have tabulated the edges, faces and vertices of shapes such as the platonic solids to thereby notice this relationship. Perhaps it took an almost childlike playfulness to discover this relationship. Yet it is all speculation. The only fact is that Euler did discover that V-E+F=2 where V, E, and F are, respectively, the vertices, edges and faces of a regular polyhedron

I first learned of Euler’s formula in a senior course on graph theory taught by the Polish graph theorist Dr. Siemion Fajtlowicz. Therefore, let me provide a few definitions before offering a compact proof that V-E+F=2 using basic graph theoretical methods.

Definition. A graph consists of a non-empty set of vertices and a set of edges, possibly empty. If an edge E exists, then it will be related to an unordered pair (a,b) of vertices in V. We may write G=(\{V\},\{E\}) to denote the graph.

A graph is finite if both the vertex set and edge set are finite. A graph that is not finite is infinite. The size of a graph is the number of vertices. The order of a graph is the number of edges. All graphs discussed in this article are finite.

Immediately note that if we are given one edge, then there exist two vertices — because an edge must connect to something and that something will always be a vertex. Two vertices are incident if they share a common edge and said to be adjacent. An edge with identical ends is called a loop while an edge with distinct ends is called a link. A graph is simple if it has no loops.

The degree d(v) of a vertex in a graph G is equal to the number of edges in G incident with v where each loop counts as two edges. Thus, a vertex with two edges has degree 2 because the degree of the other two vertices would be one each, and so the sum of the degrees of all the vertices would be 4. From this we have immediately the following two theorems.

Theorem 1. The sum of the degree of the vertices of a graph equals twice the number of edges. That is

\displaystyle \sum\limits_{i/G}{d({{v}_{i}})}=2e

proof. If a graph has no edges, then e=0 and the theorem is true because the sum of the degree of the vertices of a graph with no edges must, by definition, be zero. If a given vertex has an edge, then there must be a second vertex connected to the first vertex by the given edge and so the sum of the degree of the vertexes will be 2, even if the edge were a loop beginning and returning to a single vertex the degree of that vertex due to the loop would still be 2.

Now, each additional edge added to the graph will increase either the degree of the vertex it is connect to and add one additional vertex or else it will add one degree each to two vertices that already exist. Thus, each time an edge is added, the degree count of the vertices increases by 2. Therefore, the sum of the degree of all the vertices will always be simply twice the number of edges present.

Theorem 1.1 The number of vertices in a graph of odd degree is even.

proof. Let {{v}_{1}},{{v}_{2}} be sets of vertices where the {{v}_{1}} is of odd degree and {{v}_{2}} is of even degree. Then, from Theorem 1, we must have that

\sum\limits_{i/G}{d({{v}_{1}})}+\sum\limits_{i/G}{d({{v}_{2}})}=\sum\limits_{i/G}{d(v)}

but we have already established that

\sum\limits_{i/G}{d({{v}_{i}})}=2e

and therefore we must have

\sum\limits_{i/G}{d({{v}_{1}})}+\sum\limits_{i/G}{d({{v}_{2}})}=2e

\sum\limits_{i/G}{d({{v}_{1}})}=2e-\sum\limits_{i/G}{d({{v}_{2}})}

but

\sum\limits_{i/G}{d({{v}_{2}})}=2{{e}_{2}}

so

\sum\limits_{i/G}{d({{v}_{1}})}=2e-2{{e}_{2}}=2(e-{{e}_{2}})=2{{e}_{1}}

is even. Thus, we have that the sum of the vertices in a graph of odd degree is even. Now, we will need the following definitions to proceed.

Definition. A cycle is a closed chain of edges. A connected graph that contains no cycles is a tree.

Definition. A spanning tree of a graph G is one that uses every vertex of G but not all of the edges of G.

Every connected graph G contains a spanning tree T as a subgraph of G.

Definition. A planer graph is one that can be drawn in the plane without crossing any edges.

Definition. A face in the plane consists of both unbounded and bounded regions.

The last definition allows us to say that the number of “faces” of a finite line segment in the plane is 1, but that the number of faces of an infinite line is 2, one for each side that the line divides the plane into, and that the number of faces of a circle in the plane is 2, one corresponding to the inside and the other to the outside of the circle one being the unbounded and the other the bounded region.

Now we are ready to prove Euler’s formula as it may be stated in graph theory.

Theorem 2. If G is a connected planer graph with vertices v, edges e, and faces f, then

\displaystyle v-e+f=2

proof. Let T be a spanning tree of a graph G. Then the number of faces f=1 and the number of edges e= v – 1 is true for the spanning tree T of G and so we have v-(v+1)+(1)=2 and our formula is true. Now, G may be constructed from T by adding edges to T, but each time we do so we are adding a new face to T. Therefore, with the addition of each new edge, e will increase by 1 and f will increase by 1. Therefore, all of these additions cancel out and we have our formula.

Now, a homomorphism exists between polyhedron and graphs in that a connected plane graph can be uniquely associated with a polyhedron by making any face the flat unbounded part of the plane. Therefore, Euler’s formula is true for polyhedron. We can therefore immediately prove:

Theorem 3. Exactly five platonic solids exist.

proof. Let the number of edges and faces be n and the number of edges each vertex is incident to be d. If we multiply nf, we get twice as many edges because each edge belongs to two faces, so nf is the number of faces multiplied by the number of edges on each face. Likewise, with dv each edge is incident to two faces so that we have dv=2e so that we have the equality

nf=2e=dv

or

e=\frac{dv}{2} and f=\frac{dv}{n}

Now, placing these into Euler’s formula, we get

v+\frac{dv}{n}-\frac{dv}{2}=2

or

(2n+2d-dn)v=4n

But both v and n are positive integers and for (2n+2d-dn)v=4n to be true, we must have that

2n+2d-dn>0

or

(n-2)(d-2)<4

and so there are just five possibilities for the values of n and d and each of these corresponds to one of the five platonic solids, so that we have

n=3,d=3 is a tetrahedron
n=3,d=4 is a hexahedron also known as a cube
n=4,d=3 is a octahedron
n=3,d=5 is a dodecahedron
n=5,d=3 is a icosahedron

the 5 Platonic Solids

QED.

© 2012 Kurt Lovelace – All Rights Reserved

Graph Isomorpshism and Coloring

This week, Professor Siemion Fajtlowicz assigned two home work problems:

1. How many graphs with vertices 1 … n are there?

2. Up to isomorphism, how many graphs are there with n vertices?

3. If you invite 6 random people to a party, show that 3 of them will know each other or 3 of them will be mutual strangers — and show that this is guaranteed to always be the case — but only if you invite a minimum of 6 random people to the party. It will not be the case if we only invite 5 random people or 4 random people, et cetera.

____________________________________________________________________________________________________________________________
Question 1 and 2 may appear to be identical questions, but they are not at all identical though they are related.

Question 1 is asking for the number of elements of S. Question 2 is asking for the number of elements of the quotient G\S, a very different and much more difficult question.

Theorem. There are

\displaystyle {{2}^{\left( \begin{matrix} n \\ 2 \\ \end{matrix} \right)}}

graphs with vertex set \displaystyle \{1,2,3,...,n-1,n\} .

Proof. The question is easily answered. Given n vertexes, if we start from vertex 1 and connect an edge to each of the remaining vertexes, so that 1 goes to 2, 1 goes to 3, and so on until 1 goes to (n-1) , and 1 goes finally to n. Now, including the null edge or simply 1 itself connected to nothing, which is a legitimate graph, we have that there are n graphs. Repeating this for each additional vertex, and taking into account that the edge may originate at either one of the vertexes making for two graphs — if allowing full duplicates — then we will have that there are exactly,

\displaystyle ^{1+2+3+...+(n-1)+n}

possible graphs raised to the power of 2 to account for starting at either vertex, which gives us:

\displaystyle {{2}^{1+2+3+...+(n-1)+n}}={{2}^{\sum\limits_{i/{{\mathbb{Z}}_{+}}}{i}}}={{2}^{\frac{n(n+1)}{2}}}

Therfore, the number of graphs with vertices 1 to n are:

\displaystyle {{2}^{\left( \begin{matrix} n \\ 2 \\ \end{matrix} \right)}}

and this is simply a more compact way of writing the RHS of the previous result using binomial coefficients. QED

____________________________________________________________________________________________________________________________

Theorem. Up to isomorphism, there are

\displaystyle \frac{1}{n!}\sum\limits_{n\in \sum\nolimits_{n}{{}}}{{{2}^{o\left( \sigma \right)}}}

graphs with n vertices.

The answer to the question is much more difficult, because the answer involves some hefty but basic machinery from Group Theory and Combinatorics involving Burnside’s Lemma and Polya’s Enumeration Theorem such that this question may be reworded in those terms, so that it becomes:

How large is the set \displaystyle \sum\nolimits_{n}{{}}\backslash S where \displaystyle \sum\nolimits_{n}{{}} denotes the symmetric group on n letters and \displaystyle S is the set of graphs with vertex set \displaystyle {1,2,3,...,n-1,n} ?

The answer is

\displaystyle \frac{1}{n!}\sum\limits_{n\in \sum\nolimits_{n}{{}}}{{{2}^{o\left( \sigma \right)}}}

where \displaystyle o\left( \sigma \right) denotes the number of \displaystyle \sigma orbits on the set.

____________________________________________________________________________________________________________________________

At any party with 6 guests, either 3 are mutual friends or else 3 are mutual strangers. That is, the symmetric Ramsey Number R(3,3) = 6

If we consider just one person, then the other five must fall into one of the two classes of being either a friend or a stranger. This follows immediately from the pigeonhole principle, namely that, if m pigeons occupy n holes where \displaystyle n<m , then at least one hole contains:

\displaystyle \left\lfloor \frac{m-1}{n} \right\rfloor +1

pigeons, where \displaystyle \left\lfloor {} \right\rfloor is the greatest integer function. The proof of this follows from the fact that the largest multiple of n that divides into m is the fractional part left over after n divides m-1 or

\displaystyle \left\lfloor \frac{m-1}{n} \right\rfloor

and so for n pigeons, we get

\displaystyle n\left\lfloor \frac{m-1}{n} \right\rfloor

pigeons that could be put into \displaystyle \left\lfloor \frac{m-1}{n} \right\rfloor holes. But we have m pigeons, and so there must be more than this many pigeons in the holes.

Now, for our problem, we have two classes, friends and strangers. If we choose one person, then that leaves 5 people with whom that person is either a friend or a stranger. And so, by the pigeonhole principle, for five objects going into two classes we must have at least:

\displaystyle \left\lfloor \frac{5-1}{2} \right\rfloor +1=3

members in one of the classes. In terms of a graph theoretical viewpoint, we have, starting with one vertex extended out to the other five “people” vertexes, that:

where the red edges represent friends and the blue edges represent strangers. We easily see that, regardless of how we choose one of our 2 colors, 3 of them must be blue or else 3 of them must be red, for if we have five red, then we have met the required condition that at least 3 be red, and likewise if 4 are red, we again fulfill the requirement that at least 3 be red; and so, this whole sequence of argument applies if we swap blur for red. Therefore, we are always guaranteed that there are 3 mutual friends or else that there are 3 mutual strangers in any group of 6 people. QED

In terms of Ramsey Numbers, the statement would be written \displaystyle R(3,3)=6 .

This is utterly fascinating, because what this is really telling us it that there is a type of structure built into any random finite set. In this case, for any binary operation or else any question or property that has two values, we have it that any finite set of 6 is sufficient to support there being 3 of one or 3 of the other of that property, and that one of the two sets of 3 always exists inside of the 6 items.

This is a glimpse into a type of “deep structure” embedded within the fabric of finite sets. This is more than merely surprising, as one should not really be expecting to find any such structure whatsoever in a random set.
____________________________________________________________________________________________________________________________

Going somewhat beyond this homework problem, from experimental math studies using Mathematica, I conjecture that:

\displaystyle R(n,n)=\frac{1}{12}(3{{n}^{4}}-20{{n}^{3}}+63{{n}^{2}}-82n+48)

holds for n<=20 in a completely trivial and weak algebraic sense that the Ramsey Numbers in this range do indeed appear in this formula.

However, there is no natural or reasonable theoretical connection whatsoever between this formula and Ramsey Numbers other than the search for generating functions and sequence matching studies that I conducted. So, for n = 3 to 20 this formula yields:

\displaystyle \text{R(3,3) = 6}
\displaystyle \text{R(4,4) = 18}
\displaystyle \text{R(5,5) = }49
\displaystyle \text{R(6,6) = }116
\displaystyle \text{R(7,7) = }242
\displaystyle \text{R(8,8) = }456
\displaystyle \text{R(9,9) = }793
\displaystyle \text{R(10,10) = }1,294
\displaystyle \text{R(11,11) = }2,006
\displaystyle \text{R(12,12) = }2,982
\displaystyle \text{R(13,13) = }4,281
\displaystyle \text{R(14,14) = }5,968
\displaystyle \text{R(15,15) = }8,114
\displaystyle \text{R(16,16) = }10,796
\displaystyle \text{R(17,17) = }14,097
\displaystyle \text{R(18,18) = }18,106
\displaystyle \text{R(19,19) = }22,918
\displaystyle \text{R(20,20) = }28,634

which all fall nicely into current best-known intervals for these numbers. But these values are essentially nonsense. However, it is currently believed that \displaystyle \text{R(5,5) = }43 rather than 49. But there is no polynomial expression that yields 43 and the other lower already known numbers in the sequence of Ramsey Numbers evident from running long and large searches for such. Therefore, I believe that any meaningful approximate or asymptotic formula must be non-polynomial.

Therefore, my intuition says that there may well exist an exponential, non-polynomial expression for the Ramsey Numbers — perhaps similar to the P(n) function of Rademacher such as

\displaystyle p(n)=\frac{1}{\pi \sqrt{2}}\sum\limits_{k=1}^{\infty }{\sqrt{k}}{{A}_{k}}(n)\frac{d}{dn}\left( \frac{1}{\sqrt{n-\frac{1}{24}}}\sinh \left[ \frac{\pi }{k}\sqrt{\frac{2}{3}\left( n-\frac{1}{24} \right)} \right] \right)

where

\displaystyle {{A}_{k}}(n)=\sum\limits_{0\le m<k;\ (m,k)=1}{{{e}^{\pi i\left[ s(m,k)\ -\ \frac{1}{k}2nm \right]}}}.

But then I may be dreaming here because there need be no sequential connection between one of these numbers and the other — if each is a unique value in it’s own problem space.

What I find frustrating with papers on Ramsey Numbers that I have read is their lack of a more probing approach. We know that calculating Ramsey Numbers is NP-hard. One paper even suggested that this is Hyper-NP hard — but did not specify in what manner they meant this to be true. Most likely they were referring to the absurdly rapid exponential growth of the possible solution space. But where are the more basic insights into the nature of these numbers? Most of what we have now is not much beyond Paul Erdős work in the 1930’s!

In a recent paper on Ramsey Numbers, the physicist Kunjun Song, said: “Roughly speaking, Ramsey theory is the precise mathematical formulation of the statement: Complete disorder is impossible. or Every large enough structure will inevitably contain some regular substructures. The Ramsey number measures how large on earth does the structure need to be so that the speci ed (sic.) substructures are guaranteed to emerge.”

I think that we have yet to ask ourselves the deeper questions to get further along here. I am now researching the different ways in which the same questions may be asked, such as via Shannon limits of graphs and quantum algorithms to see what pure mathematical insight might be gleamed from these approaches. I am looking for good questions that, if properly phrased, should provide a road-map for further fruitful research.

© 2012 Kurt Lovelace – All Rights Reserved

Introduction to Graph Theory

This was the first week of my senior-level class with Professor Siemion Fajtlowicz, MATH 4315 – Graph Theory, and it was a blast!

The central question put to the class is when are two graphs isomorphic. There is nothing easy nor trivial about this question. It can be challenging to even distinguish that two simple graph representations are of different graphs, let alone of the same graph.

Also, we have been assigned the task of showing how one is to interpret the historically notable problem, first presented to and solved by Leonhard Euler in 1735, of the Seven Bridges of Königsberg in a graph theoretic manner. Euler resolved this question in the negative, but there is a lot more to it than that, as we will see in this article.

Along with this problem, we have also been assigned the Knight’s Tour problem which we are also to interpret in a graph theoretic fashion.