Graph genus γ(G): minimum handles on sphere for crossing-free embedding. γ=0 iff planar. Generalized Euler: V-E+F=2-2γ. Ringel-Youngs (1968): γ(K_n) = ⌈(n-3)(n-4)/12⌉ for n≥3. Proved the Heawood conjecture.
How to Use
Select graph:
- γ: Genus
- Euler: V-E+F=2-2γ
- Surface: Sphere/torus/...
Ringel-Youngs Theorem
γ(K_n) = ⌈(n-3)(n-4)/12⌉. Determines the genus of every complete graph. Proved the Heawood conjecture (1890→1968): chromatic number of surface S_γ = ⌊(7+√(1+48γ))/2⌋ for γ≥1.
Surfaces
Sphere (γ=0): planar graphs. Torus (γ=1): K_7 embeds. Double torus (γ=2): K_8. The complete graph K_n needs (n-3)(n-4)/12 handles. Möbius strip and Klein bottle are non-orientable surfaces.
Step-by-Step Instructions
- 1Select graph.
- 2Compute genus.
- 3Verify Euler.
- 4Identify surface.
- 5Check Heawood.