Part (i): Maximum Number of Edges in a k-Degenerate Graph
We need to determine the maximum number of edges possible in a graph with \( n \) vertices that is k-degenerate.
A graph is k-degenerate if there exists an ordering of its vertices \( v_1, v_2, \ldots, v_n \) such that for each vertex \( v_i \), the number of its neighbors with higher indices—i.e., \( |\{ v_j \in N(v_i) : j > i \}| \)—is at most \( k \). This suggests a greedy construction where each vertex connects to as many subsequent vertices as allowed, up to \( k \), to maximize the edge count.
constructing a graph as follows: order the vertices as \( v_1, v_2, \ldots, v_n \), and for each vertex \( v_i \), connect it to the next \( k \) vertices in the sequence, or all remaining vertices if fewer than \( k \) follow. Formally, \( v_i \) is adjacent to \( v_{i+1}, v_{i+2}, \ldots, v_{i+m} \), where \( m = \min(k, n - i) \), because there are \( n - i \) vertices after \( v_i \), and we take up to \( k \) of them. Let’s verify this satisfies k-degeneracy and compute the edges.
Check k-degeneracy: For vertex \( v_i \), its neighbors after it are \( v_{i+1}, \ldots, v_{i+m} \), and the number of such neighbors is \( m = \min(k, n - i) \). Since \( n - i \) is the number of vertices following \( v_i \), if \( n - i \geq k \), then \( m = k \); if \( n - i < k \), then \( m = n - i < k \). In both cases, \( m \leq k \), so the ordering \( v_1, v_2, \ldots, v_n \) satisfies the k-degenerate condition.
Count the edges: Each vertex \( v_i \) contributes edges to its subsequent neighbors. The number of edges from \( v_i \) is the number of vertices it connects to, which is \( \min(k, n - i) \).
(Note: if \( i = n \), then \( n - i = 0 \), and no edges are added, which is fine.)
The total number of edges \( e \) is the sum over all vertices: \( e = \sum_{i=1}^{n} \min(k, n - i) \)
To compute this, consider \( n - i \) as \( i \) ranges from 1 to \( n \):
- for \( i = 1 \), \( n - i = n - 1 \),
- for \( i = 2 \), \( n - i = n - 2 \),
- ...
- for \( i = n \), \( n - i = 0 \).
So, the sequence \( n - i \) runs from \( n - 1 \) down to 0, and we take \( \min(k, n - i) \) for each term. Rewrite the sum by changing variables: let \( j = n - i \), so as \( i \) goes from 1 to \( n \), \( j \) goes from \( n - 1 \) to 0. Thus:
\[
e = \sum_{j=0}^{n-1} \min(k, j)
\]
Split this sum based on where \( j \) reaches \( k \):
- For \( j = 0, 1, \ldots, k-1 \), \( \min(k, j) = j \) (assuming \( k \geq 1 \); if \( k = 0 \), the sum adjusts accordingly).
- For \( j = k, k+1, \ldots, n-1 \) (if \( n - 1 \geq k \)), \( \min(k, j) = k \).
- First part: \( \sum_{j=0}^{k-1} j = 0 + 1 + 2 + \cdots + (k-1) = \frac{(k-1)k}{2} \) (sum of first \( k \) nonnegative integers, excluding 0 if \( k = 1 \)).
- Second part: If \( n - 1 \geq k \) (i.e., \( n \geq k + 1 \)), there are terms from \( j = k \) to \( n - 1 \), each equal to \( k \). Number of terms = \( (n - 1) - k + 1 = n - k \), so the sum is \( k (n - k) \). If \( n - 1 < k \) (i.e., \( n \leq k \)), all terms use \( j \), and we adjust below.
Thus, if \( n > k \):
\[
e = \sum_{j=0}^{k-1} j + \sum_{j=k}^{n-1} k = \frac{(k-1)k}{2} + k (n - k)
\]
If \( n \leq k \), then \( n - 1 < k \), so \( \min(k, j) = j \) for \( j = 0 \) to \( n - 1 \):
\[
e = \sum_{j=0}^{n-1} j = \frac{(n-1)n}{2}
\]
Let’s unify this. The expression \( k(n - k) + \frac{k(k - 1)}{2} \) assumes \( n \geq k \), but for \( k \geq n \), the maximum edges should be that of the complete graph \( K_n \), since \( K_n \) is \( (n-1) \)-degenerate (each vertex has at most \( n - 1 \) neighbors after it in any ordering), and for \( k \geq n - 1 \), it’s achievable. Check:
- For \( k = n \): \( n (n - n) + \frac{n (n - 1)}{2} = \frac{n (n - 1)}{2} \),
- For \( k = n - 1 \): \( (n-1) (n - (n-1)) + \frac{(n-1)(n-2)}{2} = (n-1) + \frac{(n-1)(n-2)}{2} = \frac{(n-1) (2 + n - 2)}{2} = \frac{n (n - 1)}{2} \).
For \( k \geq n \), the formula gives \( \frac{n (n - 1)}{2} \) or less (if \( k > n \)), but the maximum possible is \( \frac{n (n - 1)}{2} \), matching \( K_n \). So, the maximum is:
\[
e = k (n - k) + \frac{k (k - 1)}{2}
\]
when \( k < n \), and \( \frac{n (n - 1)}{2} \) when \( k \geq n \), but the formula holds as the maximum achievable under k-degeneracy.
Lets Verif y with some examples:
- \( n = 3, k = 1 \): \( 1 (3 - 1) + \frac{1 \cdot 0}{2} = 2 \) (a path, max for trees).
- \( n = 3, k = 2 \): \( 2 (3 - 2) + \frac{2 \cdot 1}{2} = 3 \) (triangle \( K_3 \)).
- \( n = 4, k = 2 \): \( 2 (4 - 2) + \frac{2 \cdot 1}{2} = 5 \) (constructible, e.g., \( v_1 \) to \( v_2, v_3 \), \( v_2 \) to \( v_3, v_4 \), \( v_3 \) to \( v_4 \)).
This construction is maximal because adding an edge increases some vertex’s out-degree beyond \( k \) in any ordering. Thus, the maximum number of edges is:
\[
k (n - k) + \frac{k (k - 1)}{2}
\]
Part (ii): Prove H is k-Degenerate if and Only if H' is k-Degenerate
We need to prove that a graph \( H \) is k-degenerate if and only if \( H' \), obtained by removing a vertex \( v \) of degree at most \( k \) (i.e., \( \deg_H(v) \leq k \)), is k-degenerate. This is a biconditional, so we prove both directions.
Approach direction 1: If \( H \) is k-degenerate, then \( H' \) is k-degenerate
Assume \( H \) is k-degenerate with vertices \( v_1, v_2, \ldots, v_n \) such that for each \( v_i \), \( |\{ v_j \in N_H(v_i) : j > i \}| \leq k \). Let \( v = v_m \) be a vertex with \( \deg_H(v_m) \leq k \), and \( H' = H - v_m \). We need an ordering for \( H' \).
Use the ordering from \( H \), excluding \( v_m \): \( v_1, v_2, \ldots, v_{m-1}, v_{m+1}, \ldots, v_n \). For each vertex \( v_i \) in \( H' \) (i.e., \( i \neq m \)):
- Neighbors after \( v_i \) in \( H' \) are \( \{ v_j \in N_{H'}(v_i) : j > i, j \neq m \} \).
- In \( H \), neighbors after \( v_i \) are \( \{ v_j \in N_H(v_i) : j > i \} \), and since \( H' \) lacks \( v_m \), the set in \( H' \) is \( N_H(v_i) \cap \{ v_j : j > i \} \) minus \( v_m \) if \( m > i \).
- f \( m > i \), removing \( v_m \) reduces the count by at most 1 (if \( v_i \)—\( v_m \) was an edge); if \( m < i \), the set is unchanged.
- Since \( |N_H(v_i) : j > i| \leq k \), in \( H' \), it’s \( \leq k \).
Thus, \( H' \) satisfies the k-degenerate condition.
Approach direction 2: If \( H' \) is k-degenerate, then \( H \) is k-degenerate
Assume \( H' = H - v \) is k-degenerate, where \( \deg_H(v) \leq k \), and \( H' \) has ordering \( u_1, u_2, \ldots, u_{n-1} \) with \( |\{ u_j \in N_{H'}(u_i) : j > i \}| \leq k \). We need an ordering for \( H \).
Place \( v \) at the start: \( v, u_1, u_2, \ldots, u_{n-1} \).
- For \( v \): All neighbors are after it (i.e., some \( u_i \)’s), and \( \deg_H(v) \leq k \), so \( |N_H(v)| \leq k \).
- For \( u_i \): Neighbors after it in \( H \) are \( \{ u_j \in N_H(u_i) : j > i \} \). In \( H' \), it’s \( \{ u_j \in N_{H'}(u_i) : j > i \} \). Since \( N_H(u_i) = N_{H'}(u_i) \cup \{ v \} \) (if \( v \) is a neighbor), and \( v \) is before \( u_i \), the neighbors after \( u_i \) are identical in \( H \) and \( H' \), which is \( \leq k \).
This ordering satisfies k-degeneracy for \( H \).
Conclusion :Both directions hold, so \( H \) is k-degenerate if and only if \( H' \) is k-degenerate.
