Does Chromatic Number n Imply Clique on n Vertices? | Graph Theory

If a graph has chromatic number n, meaning a minimum of n colors are necessary to color it, must it contain a subgraph isomorphic to the complete graph on n vertices (Kn)? We'll see in this lesson that it is not true. We'll look at some counterexamples of graphs that have chromatic number n but have no Kn subgraph, and show how this counterexample could be used to create an induction proof for counterexamples for all chromatic numbers greater than or equal to 3.
Lesson on graph colorings: • Vertex Colorings and t...
Chromatic Number of Complete Graphs: • Chromatic Number of Co...
Thanks to Nasser Alhouti, Robert Rennie, Barbara Sharrock, and Lyndon for their generous support on Patreon!
◆ Donate on PayPal: www.paypal.me/...
◆ Support Wrath of Math on Patreon: / wrathofmathlessons
I hope you find this video helpful, and be sure to ask any questions down in the comments!
+WRATH OF MATH+
Follow Wrath of Math on...
● Instagram: / wrathofmathedu
● Facebook: / wrathofmath
● Twitter: / wrathofmathedu
My Music Channel: / @emery3050