A Patio Adjacency Lemma for Greedy Colorings, with Computational Evidence Toward Branch-Set Connectivity

We study an invariant p(G), the minimum number of palette expansions over all vertex orderings of a greedy coloring, and give a short proof that χ(G) = 1 + p(G) for every connected simple graph; while this identity is essentially the classical observation that some greedy ordering attains χ(G), we package it constructively through expansion centers. Our main contribution is the Patio Adjacency Lemma (Theorem 3.4): in any optimal greedy palette-expansion coloring with expansion centers c₁, …, cₖ, the center cⱼ has, for every i < j, a neighbor in color class Aᵢ; consequently every pair of color classes is joined by an edge with one endpoint at an expansion center. This is independently proved and verified computationally on 130,000+ graphs. We then study a branch-set construction seeded by the color classes. The Patio Adjacency Lemma makes the initial configuration pairwise-adjacent at no cost; the construction must then repair connectivity while maintaining adjacency, and we are explicit that adjacency is free only at initialization and preserved — not free — thereafter. We prove what the construction maintains unconditionally (disjointness, the adjacency invariant, and a strictly decreasing connectivity potential bounding the number of repair moves by |V(G)| − k), give a sufficient condition under which it certifies a Kₖ-minor immediately, and isolate the precise gap as Open Problem 6.1: whether an adjacency-preserving connectivity move always exists while some branch set is disconnected. We are explicit that closing this gap is equivalent to Hadwiger's conjecture for the relevant k, and we do not close it. On all 562 tested graphs the construction achieved the adjacency half — a Kₖ-complete contracted graph in which every pair of branch sets is directly adjacent — but it did not, in general, yield internally connected branch sets: in a representative audit, all branch sets were connected in only a small minority of cases while pairwise adjacency held universally. We report this as evidence for the adjacency half only, not as Kₖ-minor certificates. We make no claim about Hadwiger's conjecture for k ≥ 7, which remains open. Changes in v25: corrected Section 5.3 — the articulation-trap census was rerun with disjoint branch sets and now reports 196 of 344 graphs (the earlier count of 0 was a set-overlap bug); the trap already appears in the Mycielski graph M₄ and in every Kneser graph K(n,2), n = 5..10. Corrected Table 1 (χ(K(10,2)) = 8, Lovász 1978) and relabeled its verification column as the adjacency half; fixed the k = 5 attribution (Four-Color Theorem, Appel–Haken 1977; Robertson–Seymour–Thomas 1993) and updated the references; minor wording (e.g., "83 years"). Code: https://github.com/mizantorey/chromatic-hadwiger Project site: https://hadwiger.oryum.ai/