Here is a problem statement
“Twenty members of a club meet each evening for dinner at a round table. They plan to sit such that every member has different neighbors every evening. Find out the number of days for which this arrangement can last.”
Here is another one
“There is a list of 20 cities with roads connecting them, a salesman wants to sell his goods by visiting each city exactly once. Is that possible for a given network of cities?”
Many a times we have been given problems like above and it is not really easy to solve them if we are not equipped with the Graph Theory.
What is Hamiltonian Circuit?
This post has no concrete relation to the Euler Lines we discussed in the last post , but the definitions are pretty much similar.
A Hamiltonian circuit is a closed walk in a graph which visits each vertex exactly once. The start and end vertex (which happens to be the same) is visited twice.
A very important conclusion of this property is as follow:
In a Hamiltonian Circuit of N vertices, there would be exactly N edges. Since a Hamiltonian Circuit cannot visit the same vertex twice, hence there cannot be any loops or parallel edges. Thus all such circuits are simple graphs. And to connect each of the N vertex we need N-1 edges, to connect the first and the last vertex and close the walk, we need one more edge. Hence, N vertex Hamiltonian circuit will have exactly N edges.
If you remember from our last post, we proved that the necessary and sufficient condition for Euler Lines is that each vertex must have even degree. On the same lines if we try to establish a necessary and sufficient condition for existence of Hamiltonian Circuit in a graph we will miserably fail.
The problem of finding if a Hamiltonian Circuit exists or how many Hamiltonian Circuits exist is unsolved. This problem was posed by Rowan Hamilton, hence the name Hamiltonian Circuit.
Is this the road block?
No! There are graphs for which we can guarantee the existence of Hamiltonian Circuits and these graphs are the Complete Graphs with more than two vertices.
A complete graph is one in which each vertex is connected to every other vertex. For knowing more about Complete Graphs, please read my post on various graphs.
Note: From the properties of Complete Graphs, we know that a complete graph with N vertices has N(N-1)/2 edges. Hence, in a complete graph of N vertices where N is odd and greater than 1, there are (N-1)/2 edge disjoint Hamiltonian Circuits.
I will prove this in a while, but now if you read the above two questions, I think the answer to the seating arrangement question is pretty obvious. We have N as 21 which is odd and greater than 1.
Also, Anyone can sit with any one which means there can be edges drawn from a vertex to any other vertex in the graph (which means a complete graph). And so the number of days the arrangement can survive is (N-1)/2, which is (21 – 1)/2, that translates to 10 days. Hence, there are 10 such possible arrangements.
Now I mentioned edge disjoint circuits, what exactly is it?
If in a graph G, we can devise two paths such that no edge is common between them, then we call them edge disjoint paths. Similarly, if there are two sub graphs g1 and g2 in a graph G such that g1 and g2 have no common edges, they will be called edge disjoints sub graphs.
Proof of the above formula
Why will we have (N-1)/2 edge disjoint circuits in a complete graph of N vertices given N is odd and greater than 1?
For a complete graph of N vertices, we know that all the N-1 remaining vertices can be reached from each vertex. Also, we know that a Hamiltonian Circuit will consist of N edges. Hence, the number of edge disjoint Hamiltonian Circuit cannot exceed more than (N-1)/2.
Consider the seating arrangement case:
Without loss of generality, let us assume that the dining table is round and the total number of members is 7 (numbered from 1 to 7)
Let us analyze the above images one by one.
Day 1 they can choose to sit in any possible arrangement.
Day 2 has to be an edge disjoint arrangement w.r.t Day 1.
Day 3 has to be an edge disjoint arrangement w.r.t Day 1 and Day 2.
In each subsequent arrangement we are increasing the length of the edge by 1. Now if you observe it closely, you can very well understand that we can increase it to a certain limit (N-1)/2 .
Basically, after (N-1)/2 the edge lengths start decreasing.
In Day 1, the length of each edge (number of vertices between the endpoints) is 0. In Day 2, the length of each edge is 1.In Day 3 the length of each edge is 2 If we try and draw Day 4, the first edge would be between vertices 1 and 6 and the length would be 2 which is different from what we expect i.e. 3. Hence, we cannot draw the fourth Day arrangement.
We learnt the basics of Hamiltonian Circuits and Graphs. We also learnt that the problem of finding Hamiltonian Circuits for a simple graph is still unsolved and you have a great chance of doing some new discoveries in this areas.
In the coming posts, we will try to solve the Travelling Salesman problem.