Modern Graph Theory — Homework 5 - Sherr1.log

Loading…

Assignments: Mar 31st, 2026

Problem 1.

Given

n irrational numbers x_1, \ldots, x_n, determine the maximum number of pairs (x_i, x_j) such that x_i + x_j is rational. **Solution.** The maximum is **\lfloor n/2 \rfloor**. Partition \{x_1, \ldots, x_n\} by the equivalence relation x_i \sim x_j if x_i - x_j \in \mathbb{Q}. Each class C has the form C = \{r_C + q : q \in Q_C\} for some irrational r_C and Q_C \subset \mathbb{Q}. Fix a rational q. The pairs with sum q form a matching: if x_i + x_j = q and x_i + x_k = q, then x_j = x_k. So at most \lfloor n/2 \rfloor pairs sum to any fixed rational. Suppose x_i + x_j = q_1 and x_i + x_k = q_2 with q_1 \neq q_2. Then x_j - x_k = q_1 - q_2 \in \mathbb{Q}, so x_j \sim x_k. If also x_j + x_k = q_3 \in \mathbb{Q}, then 2x_j = q_3 + q_1 - q_2 \in \mathbb{Q}, contradiction. Thus within each equivalence class, all pairs with rational sum have the same sum value. Hence all such pairs form a single matching, giving at most \lfloor n/2 \rfloor pairs. This bound is achieved by taking \lfloor n/2 \rfloor distinct irrationals a_1, \ldots, a_{\lfloor n/2 \rfloor} and setting x_i = a_i, x_{\lfloor n/2 \rfloor + i} = 1 - a_i (plus one extra irrational if n is odd). Then x_i + x_{\lfloor n/2 \rfloor + i} = 1 for each i. ∎ **Problem 2.** Prove: In the induction proof, ex(n, K_{r+1}) is achieved uniquely by the Tur\'an graph T_{n,r}. **Proof.** **Induction on n**. For n \leq r, we have ex(n, K_{r+1}) = \binom{n}{2} achieved only by K_n = T_{n,r}. Let n > r and let G be K_{r+1}-free with n vertices and e(G) = ex(n, K_{r+1}) = e(T_{n,r}). We show G \cong T_{n,r}. Since G is extremal, it contains a K_r (otherwise we could add an edge). Let A = V(K_r) and B = V(G) \setminus A. Since G is K_{r+1}-free, each vertex in B has at most r-1 neighbors in A. Thus

e(G) = \binom{r}{2} + e(G[B]) + e(A,B) \leq \binom{r}{2} + ex(n-r, K_{r+1}) + (r-1)(n-r).

By induction, e(G[B]) \leq e(T_{n-r,r}) with equality iff G[B] \cong T_{n-r,r}. Since e(T_{n,r}) = \binom{r}{2} + e(T_{n-r,r}) + (r-1)(n-r), equality e(G) = e(T_{n,r}) requires G[B] \cong T_{n-r,r} and each vertex in B has exactly r-1 neighbors in A. Moreover, the non-neighbors in A must partition B so that G is complete r-partite with parts as equal as possible. This forces G \cong T_{n,r}. ∎ **Problem 3.** Prove: Every n-vertex graph with at least kn edges contains a path of length k. **Proof.** **Induction on n**. For n \leq k, the condition e(G) \geq kn is impossible since e(G) \leq \binom{n}{2} < kn. Let n > k and let G have n vertices with e(G) \geq kn. If G is disconnected, some component C with n' vertices has at least kn' \cdot (n'/n) > kn' edges, and we apply induction to C. So assume G is connected. If G has a vertex v with \deg(v) \leq k, then G - v has n-1 vertices and e(G-v) \geq kn - k = k(n-1) edges. By induction, G-v contains a path of length k, hence so does G. So \delta(G) \geq k+1. Let P = v_0 v_1 \cdots v_m be a longest path. If m < k, then all neighbors of v_0 lie on P. Since \deg(v_0) \geq k+1, vertex v_0 has at least k+1 neighbors in \{v_1, \ldots, v_m\}. Let v_j be the neighbor with maximum index. Then j \geq k+1 > m \geq j, contradiction. Thus m \geq k. ∎

PDF

Download the original write-up here.