MathCastle
Graph TheoryMediumGraph Coloring

Graph Coloring · Medium problem

Three managers M1,M2,M3M_1,M_2,M_3 and five employees E1,…,E5E_1,\ldots,E_5 have a supervising link whenever a manager directly oversees an employee: M1M_1 oversees E1,E2,E3E_1,E_2,E_3; M2M_2 oversees E1,E4E_1,E_4; M3M_3 oversees E5E_5. No manager oversees another manager, and no employee oversees another employee. Using König's edge-coloring theorem, what is the fewest meeting times needed so that no person attends two overlapping one-on-one meetings (two links sharing a person can't use the same time)?