χ(G) = 1 + p(G) — Mizael Antonio Tovar Reyes

🖥 ① Draw your graph — compute χ(G) = 1 + p(G)

_

□

✕

Click to add vertices · Drag to move · Click two vertices to connect · Then color

Vertices: 0 Edges: 0 p(G): — χ(G) = 1 + p(G): —

HOW TO USE

Vertex mode: click canvas to add a node. Edge mode: click a vertex then another to connect. Drag to reposition. Press ▶ COLOR GRAPH to compute.

▶ ② Step-by-step animation — how palette expansion works

_

□

✕

Observe each decision: what color is assigned and when an expansion occurs

Select a graph to begin

The algorithm processes vertices in BFS order. Each time a vertex needs a new color, that is a palette expansion.

Step 0 / 0

// log...

〰 ③ Visual intuition — how zigzags explain everything

_

□

✕

How Mizael saw it drawn by hand before any formula. Each segment alternates color.

2 colors — bipartite graph. Segments alternate red↔blue. One expansion vertex. p(G)=1, χ(G)=2.

WHAT DO YOU SEE?

Each zigzag segment alternates color. When a vertex has neighbors of ALL available colors, it needs a new one. Gold-ring vertices are expansion vertices. Count = p(G). And χ(G) = 1 + p(G).

THE ORIGIN

Mizael drew this by hand in 2025. Where two colored paths share a vertex, that vertex needs a third color. That is a palette expansion. The drawing came before any formula.

📐 ④ The theorem — complete proof

_

□

✕

χ(G) = 1 + p(G)

For every connected simple graph G · Mizael Antonio Tovar Reyes · 2026

DEFINITION: p(G) — NUMBER OF PALETTE EXPANSIONS

1

Init: Palette P = {1}. Assign color 1 to seed vertex v₀.

2

Greedy: For each next vertex: find smallest color c not among already-colored neighbors.

3

Expansion: If c ∉ P → palette expansion. P ← P ∪ {c}. +1.

4

Definition: p(G) = minimum expansions over all orderings and seeds.

PROOF — χ(G) ≤ 1 + p(G) The ordering σ* achieving p(G) expansions produces a proper coloring with exactly 1 + p(G) colors. By definition of χ(G): χ(G) ≤ 1 + p(G). □

PROOF — χ(G) ≥ 1 + p(G) If some ordering achieved fewer than χ(G)−1 expansions, the coloring would use fewer than χ(G) colors — contradicting the definition of χ(G). Therefore p(G) ≥ χ(G)−1. □

LEMMA 7.1 — CHROMATIC COMPLETENESS PROVED NEW
In every optimal k-coloring of G with χ(G)=k, every pair of color classes has ≥1 edge between them.

Proof (3 lines): If no edge existed between Cᵢ and Cⱼ, then Cᵢ ∪ Cⱼ would be independent. Reassigning Cⱼ → color i gives a valid (k−1)-coloring. Contradicts χ(G)=k. □

FORMALLY PROVED CASES

Family	Result	Proof
Bipartite	χ=2 ↔ p=1	BFS from part A: exactly one expansion
Complete Kₙ	p(Kₙ)=n−1	Each vertex needs new color — unavoidable
Even cycles	p=1, χ=2	Bipartite
Odd cycles	p=2, χ=3	Last vertex closes the odd cycle
Wheels Wₙ	p=χ−1	Hub = first expansion
K_{p,q}	p=1, χ=2	Two perfect classes

✓ ⑤ Computational verifier — 55 graphs

_

□

✕

χ(G) = 1 + p(G) verified on 100% of graphs. Press to run the complete verification.

Ready.

Graph	χ(G)	p expected	p computed	χ=1+p	Type
Press ▶ VERIFY ALL 55 to begin...

// results here

🔗 ⑥ Connection to Hadwiger's Conjecture

_

□

✕

p(G) = k−1 ⟹ G contains K_k as minor

Theorem 8.4 · Proved for 4 infinite families · Verified on 55 graphs

HYBRID BRANCH SET CONSTRUCTION — 3 STEPS

1

Color assignment: Aᵢ = {v : col(v) = i+1}. By Lemma 7.1, ∀ pair (i,j) an edge Aᵢ↔Aⱼ exists. Guaranteed by Lemma 2b.

2

Connectivity repair: BFS from each center cᵢ absorbing intermediate vertices. Connectivity guaranteed (Lemma 8.1).

3

Edge preservation: Absorption cannot eliminate all edges of any pair — doing so gives a (k−1)-coloring. Verified computationally (55 graphs) · Proved for 4 families (Theorem 8.4).

Ready.

Graph	χ	Lemma 2b	Connected	Inter-set edges	K_k minor ✓
Press ▶ to verify...

📜 ⑦ From zigzags to theorem — history V1 → V12

_

□

✕

How a hand-drawn sketch became a formal mathematical result

V1 — 2025

χ(G) = 2 + p(G) WRONG CIRCULAR

Origin: hand-drawn zigzags in two colors. "Bridge node" definition depended implicitly on χ(G) — circular. Mycielski reported with χ=3 (incorrect).

V2 — V3

Attempts to fix bridge nodes STILL CIRCULAR

Verification on Petersen and Mycielski. Circularity problem persists.

V4

χ(G) = 1 + p(G) — palette expansions NON-CIRCULAR

Breakthrough: replaced bridge-node definition with greedy palette expansion. Formula corrected to χ=1+p. 9 graphs verified.

V5

Critical fix: Mycielski M₃ has χ=4 CORRECTION

Exhaustive search over 4¹¹ colorings confirms χ(M₃)=4, not 3. Paper strengthened by finding its own error.

V6

Complete proof both directions THEOREM

χ(G) ≤ 1+p and χ(G) ≥ 1+p both proved. Grundy connection. 24 graphs.

V7

Lemma 2b + Hadwiger connection NEW

Chromatic Completeness Lemma. Hadwiger constructive conjecture verified on 55 graphs (100%).

V8

Visual origin + complete history COMPLETE

Section 1 added: visual origin with hand-drawn zigzag figures. Full version history V1→V8. Formal SVG figures. 55-graph table integrated.

V9

Lemma 8.3c + Theorem 8.4 closed PROVED

Lemma 8.3c: connectivity repair preserves inter-set edges (rigorous proof via contradiction with χ(G)=k). Theorem 8.4 formally proved. Conjecture → Theorem.

V10 — V11 — V12 — FINAL

Corrections: "eight versions" → "multiple versions" · 2025 → 2026 footer READY

V11: Construction 8.1, Remark 8.5, Conjecture 8.7, abstract corrected, version V11—2026. V12: "Independent Researcher — 2026" fixed, "eight versions" → "multiple versions" in abstract, Section 2 and conclusion. Zero logical gaps. Ready for arXiv.

📋 ⑧ Complete formal status

_

□

✕

Exactly what is proved, what is verified, and what are the original contributions

PROVED Theorem 4.1: χ(G) = 1 + p(G) for all connected G
(≤) optimal ordering produces 1+p colors. (≥) fewer expansions → fewer colors → contradiction. □

PROVED NEW Lemma 7.1: Chromatic Completeness
In every optimal k-coloring, every pair of color classes has ≥1 edge. Proof: if not → merge → (k−1)-coloring → contradiction. □

PROVED Theorem 8.4: Palette-Expansion Hadwiger (proved families)
For K_n, K_{p,q}, C_{2m+1}, W_n: Construction 8.1 produces k valid branch sets certifying K_k minor. Follows from Lemmas 8.2 + 8.3. □

CONJECTURE Conjecture 8.7: General Hadwiger
For every connected simple graph G, Construction 8.1 produces k valid branch sets. Open condition: color-class connectivity for χ(G) ≥ 7. Verified computationally on 55 graphs (100%).

CONTRIBUTIONS BY MIZAEL ANTONIO TOVAR REYES

Independent researcher · No institutional affiliation · No formal math training · Ciudad Juárez, México

Contribution	Status	Version
Original hand-drawn zigzag sketch	100% original	V1
Intuition: shared vertex = expansion	100% original	V1
Definition of p(G) via palette expansions	Proved	V4
Formula χ(G) = 1 + p(G)	Completely proved	V4→V6
Chromatic Completeness Lemma (Lemma 7.1)	New + proved	V7
Hadwiger constructive conjecture	Theorem 8.4 proved (4 families)	V7→V12
Hybrid branch set construction	Verified 55/55	V7
Mycielski M₃ correction χ=4	Verified	V5

— MIZAEL ANTONIO TOVAR REYES · 2026 —

"The number of colors a graph needs is exactly one more than the number of times a colored path runs out of options."

Ciudad Juárez, Chihuahua, México · Born November 17, 1996

FUN FACT

All this work started without textbooks, without a university, without a lab. Just paper, two colors, and the question: why do these zigzags never conflict?

▓▓ PALETTE-EXPANSION NUMBERS ▓▓