Running in circles
Even though the title would work for the reason this blog post is out so late, it should have been published Monday evening, I still like to do a little math (it’s better for my blood pressure anyways).
But on to the blog post. Last week I had a short chat with a colleague who is working on graph theory, not my field of research but I really like it. She was stuck on the proof of a property which seems to be rather obvious:
If I understood her correctly it was for an exercise for her students, so if you are here because you googled the problem set “Please try to solving it on your own!” Otherwise I hope you learn something.
Ok now so let’s first clear up for everybody what we are talking about.
(Undirected) Graph
A graph is a tuple with being a set the vertices or nodes, and with a set of edges.
If you are a mathematician or at least have a good ability to read mathematical definitions, this might be enough for you and you can skip the next paragraph.
For anybody else let me try to explain what this means. First we have a set of vertices . Every vertex is just a “thing” that we can somehow connect with some other “thing” (vertex) by a relation e.g. train stations, people or dots. The second part, the edges , are precisely these relations, every edge () connects exactly two “things” (vertices) with one another (), going on with the examples above, you can think of an edge as train tracks connecting two train stations, friendships connecting two people or simply a line connecting two dots. In the special case stated above we can’t distinguish between an “origin” and a “target” of the relations, so they are symmetrical which only means if and are train stations and there is a track between them we can’t say the track only goes from to but not the other way around. There is one more technicality we don’t allow loops e.g. one vertex having an edge going from back to is forbidden. For the reminder of this exercise this makes no big difference, but makes the formulation above a little easier.
For obvious reasons we resort to showing graphs as dots and lines between them. So here is an example:
Here we have the vertices and the edges . Note that I could have written as well, since sets have no inherent order, which is what I said above with no “origin” and “target”.
But let’s to go on with our property from above. For a mathematical formulation we need one more thing:
Path
For a Graph a path is sequence of vertices such that for every two vertices holds. A path with is called a cycle.
Once again a more intuitive way to state that. A path is probably exactly what you would think it is, if you can go from the first vertex in the sequence to the second via an edge then to a third an so on you have a path. In our example from above is a path since we can go from to with the edge from to via and from to with .
A cycle is then, probably not to you surprise, a path that starts and ends at the same vertex.
So now once again to our problem. A mathematical formulation of the above is:
In the above example it is easy to see what our property states, the graph has four vertices and three edges, so one less edge than vertices and has no cycle. However you can’t add any edge between two of the vertices without introducing one.
Two remarks here:
- The property does not state that we can’t make a cycle in a graph with less edges than vertices. It only states that if we have at least as many edges as vertices we are guaranteed to have a cycle.
- From your math education in school you might remember that any number of example can’t be a proof that this holds in general.
In this case however the property holds and now let’s proof that.
Proof
First let’s give an equivalent formulation:
I trust in you seeing that this is equivalent formulation to the one above.
Our proof now proceeds in two steps:
- We proof that there is at least on vertex in any cycle-free graph that has at most one edge connecting it to one other vertex. Or mathematically stated .
- We proof by induction, that is, if we have a proof that our property holds for a/all smaller graph(s) we can proof it for a graph having one more vertex.
For the first part.
Lemma
Proof (by reductio ad absurdum)
We proof this lemma by reductio ad absurdum or contradiction, that is, we say: “There is a cycle-free graph that has no such vertex” and than show that this is a contradiction, which leads to understanding that our initial idea has to be wrong and the opposite has to be true, which is what we wanted to proof in the first place. Here we go:
Claim: There is a cycle-free graph with where all vertices have .
If we have such a graph, then we construct a path as follows: We take any vertex , since this vertex has there is an edge . And we can select as the second vertex, and so on. Since for all vertices we can always select such that $v_{i-1} \not= v_{i+1}$, so the incoming edge is different from the outgoing edge. But now we have a problem contains vertices (just count from to ) but only contains vertices, so two vertices in this path need to be the same. Which means, yes you guessed it, there has to be a cycle. So the graph can’t be cycle-free and we have our contradiction and by that know that our lemma holds.
Theorem
Now to our main theorem:
We will proof this by induction, which goes as follows, we first proof our theorem directly for the base instance, the smallest graph we want our property to hold for. Since we didn’t state otherwise this is the graph with one vertex. Following that we construct a proof for a graph with vertices given that we have a proof for a graph with vertices.
So let’s see how this goes. We start with the base case.
Proof
Base case: A graph with only one vertex can obviously have no edge without having a cycle.
This takes care of the base case.
Induction hypothesis: For every graph with , if is cycle-free holds.
Induction step: Let be a cycle-free graph with vertices. Than, due to our lemma from above, contains at least one node with . We construct a new graph , where , so we remove from and we construct by removing all edges connecting with any other vertex . Obviously , since we removed 1 vertex, and , since we removed at most one edge, due to . As we couldn’t have added a cycle by removing one vertex is also cycle-free. We can now use the induction hypothesis, because only contains vertices and is cycle-free. By that we know , therefore .
And we are done. The rest is taken care of by the induction principle. Since we have the base case, we can use the induction step to get a solution for two vertices, after we have that we can continue for three, four and so on.
I hope some of you at least tried to suffer through this and have learned a thing or two. And if this was a problem set for one of your math courses, I’m glad I could help, but please try to do your problem sets on your own. You really need the training to sharpen your brain and trust me I know how hard it is to do this in the beginning.