Graph colouring
Graph theory · Mathematics
Study notes
Q: Color the square ABCD (cycle C₄) with fewest colors. A and C not adjacent: share color 1. B and D share color 2. 2 colors suffice: χ(C₄) = 2 (even cycle = bipartite!). Odd cycle C₅ needs 3: alternate 1,2,1,2 then stuck - vertex 5 needs color 3!