Let us call the mathematicians A, B, C, D, E, and denote the time intervals that each was asleep A1, A2, B1, B2, on so on. We define a graph with vertices corresponding to these 10 intervals. In the graph, we join by an edge any two vertices corresponding to overlapping intervals. 5 mathematicians can be combined in C(5, 2) = 10 pairs, so the graph has at least 10 edges. It is well known that a graph with N nodes and more than (N - 1) edges is bound to have a cycle, which tells us that our graph does have one.
An application of graph theory has delivered a cycle of intervals: a finite sequence of intervals in which any two successive intervals overlap as are the first and the last. We show by induction that in a cycle there are three overlapping intervals, i.e. intervals with a common point.
We start with a cycle of three intervals, for which the claim is next to obvious. One has to consider just a couple of possible configurations to make a convincing case.
Assume the claim has been proven for (k-1)-cycles and consider a cycle a1, ..., ak, k > 3, of overlapping intervals. Let a be the union of a1 and a2, and consider the sequence a, a3, ..., ak of k-1 intervals. The sequence is a (k-1)-cycle of overlapping intervals, which by our assumption contains three intervals with a common point. If a is not among the three we are done. Otherwise, there are intervals b and c that share a point with a. The point belongs to at least one of a1 or a2. Which proves the claim.
This can easily be proved by induction. A tree with two nodes has a single edge, naturally. For a bigger tree, pick up a node and a path that starts there. In the absence of cycles, the path terminates at a node incident to a single edge. Such a node is called a leaf. If we remove a leaf with the adjacent edge, the remaining graph will remain a tree with one node and one edge less, which allows us to proceed with the inductive step.
A forest with N nodes and k trees (k connected components) has N - k edges.
Copyright © 1996-2008 Alexander Bogomolny