In this video we begin by showing that the chromatic number of a tree is 2. Yet, if the chromatic number of a graph is 2, this does not imply that the graph is a tree. We then prove that the chromatic number of a graph is 2 if and only if the graph is bipartite.
-- Bits of Graph Theory by Dr. Sarada Herke.
Related videos:
https://youtu.be/RatkBWHUSqo - FAQs: 04. Isomorphism vs Homomorphism
https://youtu.be/YiGFhWxtHjQ - GT: 19. Graph is Bipartite iff No Odd Cycle
