Discrete Math II - 10.8.S1 Graphs and Groups: Burnside’s Lemma

This content is not covered in your textbook, but it is an important element in graph coloring. While its roots are in group theory, which we haven't yet learned, we can still benefit from the applications in graph coloring.

Video Chapters:
Intro 0:00
A Different Kind of Graph Coloring 0:27
Taking Away the Labels 1:50
3-D Motion of a Square 5:23
Stabilizers 10:57
Burnside's Lemma 17:00
Looking at Burnside Another Way 19:18
Burnside Practice 22:04
Another Burnside Practice 25:10
Up Next 28:10

[SharanUday-mq]

Here's a cool alternative to solve the last problem: interpreting the problem as choosing 3 edges from n different colours with repetition. It turns out that for any given combination of 3 out of the n colours, that represents exactly 1 configuration (thanks to the symmetries of the given reflections/rotations in 3D space). This means you can solve this problem as a combinations with repetition problem using multichoose: (n + 3 - 1)C(3) = (n + 2)C(3) or also (n + 3 - 1)C(n + 3 - 1 - 3) = (n + 2)C(n - 1)