Weak Perfect Graph Theorem

A proof of the weak perfect graph theorem.

------------------

Timetable:
0:00 - Introduction
0:34 - Graph complement
0:49 - Clique and independent set
1:32 - Induced subgraph
1:53 - Chromatic number
2:08 - Perfect graph
2:24 - Observations
3:29 - Lemma 1
4:55 - Lemma 2
6:31 - Weak perfect graph theorem
9:41 - Strong perfect graph theorem
10:23 - Outro

------------------

Source code:
https://github.com/xiaoxiae/videos/tr...

Music:
Maisie Dreamer by Blue Dot Sessions: https://app.sessions.blue/browse/trac...

Software used:
Manim (animations): https://github.com/ManimCommunity/manim/
Kdenlive (video): https://kdenlive.org/en/
ffmpeg (video): https://ffmpeg.org/
arecord (audio): https://linux.die.net/man/1/arecord
sox (audio): http://sox.sourceforge.net/

Social media:
Website (for other things I'm up to): https://slama.dev/
Patreon (if you'd like to support me):   / ytoms  

Special thanks to Jakub Medek, Matěj Kripner and Martin Koutecký for help with catching errors and providing feedback.

------------------

[CZ] Martin Koutecký's lecture on Combinatorics and Graph Theory:
https://research.koutecky.name/db/tea...

[EN] Padraic Bartlett's notes on the perfect graph theorem:
http://web.math.ucsb.edu/~padraic/mat...
http://web.math.ucsb.edu/~padraic/mat...

[EN] The Strong Perfect Graph Theorem proof:
http://www.columbia.edu/~mc2775/perfe...