ALG-B2-M01-P026 Degrees of adjacent vertices

Hint 1. Split vertices into classes \(X_i\) by degree.

Hint 2. Consider the maximum degree \(m\): cases \(m\le k-1\), \(m\ge k+1\), \(m=k\).

Answer: \(k(k-1)\). Construction: take one isolated vertex, split the remaining vertices into sets \(X\) and \(Y\) of sizes \(k\) and \(k-1\), and connect every vertex of \(X\) to every vertex of \(Y\). Then vertices in \(X\) have degree \(k-1\), vertices in \(Y\) have degree \(k\), the condition holds, and there are \(k(k-1)\) edges.

Now prove the upper bound. Let \(X_i\) be the set of vertices of degree \(i\), and let \(m\) be the maximum degree. If \(m\le k-1\), then \(2E\le2k(k-1)\), so \(E\le k(k-1)\).

If \(m\ge k+1\), choose a vertex of degree \(m\). All its neighbours have degree \(m-1\), so \(|X_{m-1}|\ge m\). Any vertex in \(X_{m-1}\) has \(m-1\) neighbours in \(X_m\cup X_{m-2}\), so the classes \(X_{m-1},X_m,X_{m-2}\) contain at least \(m+(m-1)>2k\) vertices, impossible.

It remains to consider \(m=k\). Edges connect only adjacent degree classes, so the graph is bipartite with parts \(Y=X_k\cup X_{k-2}\cup\cdots\) and \(Z=X_{k-1}\cup X_{k-3}\cup\cdots\). On one hand, \(E\le k|Y|\); on the other, \(E\le(k-1)|Z|\). If \(|Y|\le k-1\), then \(E\le k(k-1)\). If \(|Y|\ge k\), then \(|Z|\le k\), so \(E\le(k-1)k\). The upper bound is proved.

A. Source analysis. Main objects: inequalities, order, an extremal element, or an invariant. The obvious first move usually gives only a local estimate. The hidden observation is to choose the right nondecreasing quantity, or to add/multiply inequalities only after signs are controlled. The needed step is an ordering, an invariant, a product transformation, or a boundary case.

F. Difficulty justification. Regional level 7: this is a counting bound with three cases according to the maximum degree.

G. Why this is not a one-step exercise. The construction does not prove maximality; the upper bound needs degree classes.