Let be five points on a circle; some segments are drawn between the points so that each of the pairs of points is connected by either zero or one segments. Determine the number of sets of segments that can be drawn such that: - It is possible to travel from any of the five points to any other of the five points along drawn segments. - It is possible to divide the five points into two nonempty sets and such that each segment has one endpoint in and the other endpoint in .
Solution
First we show that we can divide the five points into sets and according to the second condition in only one way. Assume that we can divide the five points into and . Then, let , and . Since and partition the set of five points, also partition the set of five points. Now, according to the second condition, there can only be segments between and and between and . Therefore, the only possible segments are between points in and , or between points in and . Since, according to the first condition, the points are all connected via segments, it must be that or . If , then it follows that and . Otherwise, if , then and . In either case, and are the same partition of the five points, as desired. We now determine the possible sets of segments with regard to the sets and . Case 1: the two sets contain 4 points and 1 point. Then, there are ways to partition the points in this manner. Moreover, the 1 point (in its own set) must be connected to each of the other 4 points, and these are the only possible segments. Therefore, there is only 1 possible set of segments, which, combining with the 5 ways of choosing the sets, gives 5 possible sets of segments. Case 2: the two sets contain 3 points and 2 points. Then, there are ways to partition the points in this manner. Let be the set containing 3 points and the set containing 2 points. We consider the possible degrees of the points in . - If both points have degree 3, then each point must connect to all points in , and the five points are connected via segments. So the number of possible sets of segments is 1. - If the points have degree 3 and 2. Then, we can swap the points in 2 ways, and, for the point with degree 2, we can choose the elements of it connects to in ways. In each case, the five points are guaranteed to be connected via segments. Hence 6 ways. - If the points have degree 3 and 1. Similarly, we can swap the points in 2 ways and connect the point with degree 1 to the elements of in ways. Since all five points are connected in all cases, we have 6 ways. - If both points have degree 2. Then, in order for the five points to be connected, the two points must connect to a common element of . Call this common element . Then, for the other two elements of , each one must be connected to exactly one element of . We can choose in 3 ways, and swap the correspondence between the other two elements of with the elements of in 2 ways. Hence 6 ways. - If the points have degree 2 and 1. Then, in order to cover , the point with degree 2 must connect to 2 points in , and the point with degree 1 to the remaining point in . But then, the five points will not be connected via segments, an impossibility. - If both points have degree 1. Then, similar to the previous case, it is impossible to cover all the 3 points in with only 2 segments, a contradiction. Combining the subcases, we have possible sets of segments with regard to a partition. With 10 possible partitions, we have a total of possible sets of segments. Finally, combining this number with the 5 possibilities from case 1, we have a total of possibilities, as desired.