Lesson 10

Let \(W_{1}=V(H)\cap V_{i}\) and \(W_{2}=V(H)\cap V_{i+1}\). If one of these sets has size \(1\), then \(H\) is a star and certainly \(e(H)\le v(H)\le 2\ell v(H)\). Thus, assume \(|W_{1}|,|W_{2}|\ge 2\).

Choose a spanning tree \(T\) of \(G'\) rooted at \(c\), where each vertex outside \(V_{0}\) is connected to one parent in the previous level. Let \(a\in V_{h}\) be a vertex of largest possible level \(h\) such that all vertices of \(W_{1}\) are descendants of \(a\) in \(T\). Since \(|W_{1}|\ge 2\), we have \(h<i\). Choose a child \(b\in V_{h+1}\) of \(a\) such that at least one path from \(a\) to a vertex of \(W_{1}\) goes through \(b\). By the choice of \(a\), not all such paths go through \(b\).

Now color the vertices of \(H\) with three colors: \[\rho(x)= \begin{cases}0, & x\in W_2,\\ 1, & x\in W_1\text{ and the }ax\text{-path in }T\text{ goes through }b,\\ 2, & x\in W_1\text{ and the }ax\text{-path in }T\text{ does not go through }b.\end{cases}\] All three colors appear.

Set \[t=2(\ell-i+h).\] Since \(i<\ell\), we have \(t\ge 2\), and the number \(t\) is even. If the coloring \(\rho\) were \(t\)-periodic, then it would use at most two colors: for \(t=2\) this is the corollary above; for \(t>2\) it follows from one of the lemmas shown above, since \(e(H)>2\ell v(H)\ge t v(H)\). Therefore \(\rho\) is not \(t\)-periodic.

Hence there is a simple path \(P\) of length \(t\) in \(H\) whose endpoints have different colors. Since \(H\) is bipartite with parts \(W_{1}\) and \(W_{2}\), and \(t\) is even, both endpoints of \(P\) lie in the same part. They cannot both lie in \(W_{2}\), because all vertices of \(W_{2}\) have color \(0\). Thus, there exist \(x,y\in W_{1}\) with \(\rho(x)=1\), \(\rho(y)=2\), joined by a path \(P\) of length \(t\) in \(H\).

Let \(Q\) be the \(ax\)-path in \(T\) and let \(S\) be the \(ay\)-path in \(T\). The path \(Q\) goes through \(b\), while \(S\) does not; since \(T\) is a tree, the paths \(Q\) and \(S\) do not meet except at \(a\). Also, they do not meet \(P\) except at \(x\) and \(y\), because all internal vertices of \(Q\) and \(S\) lie on levels below \(i\). Therefore \(P\cup Q\cup S\) is a cycle. The diagram below shows the three paths.

The length of this cycle is \[2(i-h)+t=2(i-h)+2(\ell-i+h)=2\ell.\] This contradiction proves that \(m_{i} \le 2 \ell (|V_{i}| + |V_{i + 1}|)\) for \(i < \ell\).