Some interesting exercises from "Invitation to Discrete Mathematics"

Note: This writing is/was written on March 10, 2025, which was the 61th birthday of the Czech mathematician Jiri Matousek - one of the two authors of "Invitation to Discrete Mathematics". Problem 27/77 was added on April 5, 2025. Problem 10/137 was added on April 6, 2025. 

10/24: Let M be a set of real numbers, such that any nonempty subset of M has a smallest number and also a largest number. Prove that M is necessarily finite. 

Solution: Assume that M is infinite. Since M is a subset of itself, it has a smallest number A and a largest number B. Consider the sequence of sets M(0), M(1), ..., M(n), ... defined as follows: 
   i) M(0) = M; 
  ii) For each i, M(i + 1) is obtained by removing the smallest element (called a(i)) from M(i). 
   We have A = a(0) < a(1) < a(2) < ... Moreover, this sequence is bounded above by B, thus it has a limit L. Let X be the set of all numbers of the form a(n). Since the limit of this sequence is L, L is the supremum of X. Moreover, X has a largest element, thus L belongs to X. In other words, there exists a positive integer N such that a(N) = L. However, this means that a(N + 1) > L and a(n) > a(N + 1) > L for all n > N + 1, which is a contradiction. 
   This contradiction shows that our assumption is wrong and M is necessarily finite. 

27/77: Count the number of linear extensions for the following partial orderings: 
   a) X is a disjoint union of sets X(1), X(2), ..., X(k) of sizes r(1), r(2), ..., r(k), respectively. Each X(i) is linearly ordered by <=, and no two elements from the different X(i) are comparable. 
   b) The Hasse diagram of (X, <=) is a tree as in the following picture. The root has k sons, the i-th son has r(i) leaves. 

Solution: The "finite version" of linear extension might be considered as a queue, and each linear extension is a way to arrange all the elements into the queue such that certain conditions are satisfied. 
   a) Firstly, we must choose which positions in the queue are for elements of X(1), X(2), ..., X(k). For example, we might firstly require that the smallest element should be from X(1), the second smallest element should be from X(2), ... For each such choice, there is a unique way to arrange all the elements of the same set to the chosen positions so that the order is preserved. The number of such choices is (r(1) + r(2) + ... + r(k))!/[r(1)!*r(2)!*...*r(k)!]. 
   b) For each i = 1, 2, ..., k, let X(i) be the set consisting of the i-th son and its r(i) leaves. Similarly as in a), the number of ways to determine which positions in the queue are for elements of X(1), X(2), ..., X(k) is (r(1) + r(2) + ... + r(k) + k)!/[(r(1) + 1)!*(r(2) + 1)!*...*(r(k) + 1)!]. For each such choice, the r(i) leaves of the i-th son can be permuted arbitrarily. Therefore, the number of linear extensions is (r(1) + r(2) + ... + r(k) + k)!*r(1)!*r(2)!*...*r(k)!/[(r(1) + 1)!*(r(2) + 1)!*...*(r(k) + 1)!].

10/137: We say that a graph G = (V, E) is randomly Eulerian from a vertex v(0) if every maximal tour starting at v(0) is already a closed Eulerian tour in G. That is, if we start at v(0) and draw edges one by one, choosing a continuation arbitrarily among the yet unused edges, we can never get stuck. (It would be nice if art galleries or zoos were randomly Eulerian, but unfortunately they seldom are. The result in part (c) below indicates why.)
   a) Prove that the following graphs are randomly Eulerian from the indicated v(0). In fact, these graphs are not randomly Eulerian from some other vertices, but the book seemed not to explain this point explicitly. 

   b) Show that the graphs below are not randomly Eulerian from the indicated v(0). 

   c) *Prove the following characterization of randomly Eulerian graphs. A connected graph G = (V, E) all of whose vertices have even degree is randomly Eulerian from a vertex v(0) if and only if the graph (V\{v(0)}, {e in E: v(0) is not an endpoint of e}), which is the induced subgraph of G on V\{v(0)}, contains no cycle. 

Solution: As it is easy to solve a) and b) thanks to the characterization in c), only the solution to c) is presented here. Moreover, for simplicity, this solution will use the short term "even graph" for every graph all of whose vertices have even degree. If the induced subgraph of G on V\{v(0)} contains a cycle, remove this cycle from the graph. The resulting graph is still an even graph (this graph is not necessarily connected). Pick a connected component of this graph containing v(0). This component has an Eulerian cycle, thus we might follow this cycle, starting from v(0) and finally get stuck before going through the edges in C. 

                                                         We will get stuck if we start from v(0) and travel along the red cycle

   If the induced subgraph of G on V\{v(0)} contains no cycle, it is a (disjoint) union of trees. Starting from v(0) and going through the edges in E arbitrarily, we visit the vertices/edges in one of these trees and then come back to v(0). Removing this cycle still yields an even graph, and its induced subgraph on V\{v(0)} still contains no cycle. This process won't terminate until all edges are visited, since for each tree in the induced subgraph on V\{v(0)}, the vertices of degree 1 must be adjacent to v(0) so that its degree in G is an even number. 

7/158: King Uxamhwiashurh had 4 sons, 10 of his male descendants had 3 sons each, 15 had 2 sons, and all others died childless. How many male descendants did King Uxamhwiashurh have? 

Solution: This problem can be considered as a tree with King Uxamhwiashurh as its root, the children of each vertex represents the sons of the corresponding person. This tree is exactly the same as the genealogy tree in real life. We reformulated the assumptions as follows: 
   i) King Uxamhwiashurh had 4 sons -> The degree of the root is 4
   ii) 10 of his male descendants had 3 sons each -> The tree has 10 other vertices with 4 neighbors (including 3 sons and the corresponding person's father)
   iii) 15 of his male descendants had 2 sons each -> The tree has 15 vertices with 3 neighbors (including 2 sons and the corresponding person's father)
   iv) All others died childless -> The remaining vertices are leaves
   Let m be the number of leaves in this tree. The number of vertices of this tree is m + 15 + 11 = m + 26, while the number of edges of this tree is (4*11 + 3*15 + 1*m)/2 = (m + 89)/2. Solve the equation 2(m + 26) = m + 89, we obtain m = 37. The number of male descendants that King Uxamhwiashurh had is 37 + 10 + 15 = 62. 

7/233: Let n be a natural number that is not divisible by the square of any integer greater than 1. Determine the maximum possible size of a set of divisors of n such that no divisor in this set divides another. 

Solution: Let n = p(1)p(2)...p(k), where p(1), p(2), ..., p(k) are different prime numbers. For each divisor of n, define its associate set to be the set of all index i in {1, 2, ..., k} such that p(i) divides that divisor. Then, a divisor is determined uniquely by its associate set. Moreover, a divides b if and only if the associated set of a is a subset of the associated set of b. This problem can be reformulated as determining the largest size of a family of subsets of {1, 2, ..., k} such that no set in this family is a subset of another set in the same family, which can be solved easily by Sperner's Theorem. 

7/270 (Hard): Is it possible to arrange 8 bus routes in a city so that
   (i) If any single route is removed (doesn't operate, say) then any stop can still be reached from any other stop, with at most one change, and
   (ii) If any two routes are removed, then the network becomes disconnected?