Graph TheoryMediumGraph Coloring
Graph Coloring · Medium problem
Seven people sit around a circular table, each one acquainted with the two people next to them (forming a ring of acquaintance). One extra pair — the two people three seats apart in one direction — happens to ALSO be acquainted. Acquainted people must be assigned different colored name tags. What is the fewest colors needed?