NOTE: At 6:30 I describe what it means for a graph to be "k-colorable". The definition I give is common, but not formal enough to avoid some possible confusion. At 7:47 I say a graph cannot be k-colorable for k greater than its number of vertices, since k colors could not be used in a coloring - there simply aren't enough vertices to accommodate k colors if k is greater than the number of vertices. However, this "upper bound" is not common in the usage of the term "k-colorable". Especially as we move on to discussing chromatic polynomials. Often it may be convenient to say a graph is k-colorable for ANY integer greater than equal to its chromatic number. So while a complete graph on 3 vertices has chromatic number 3, for example, we could say it is k-colorable for any number greater than or equal to 3. Even though we couldn't color it with 10 distinct colors, a set of 10 colors would be sufficient (we just wouldn't use them all), so we may say it is 10-colorable anyways. Always make sure you understand the definitions being used, and I apologize if this causes any confusion! Support the production of this course by joining Wrath of Math as a Channel Member for exclusive and early videos, original music, and upcoming lecture notes for the graph theory series! Plus your comments will be highlighted for me so it is more likely I'll answer your questions! ruclips.net/channel/UCyEKvaxi8mt9FMc62MHcliwjoin Graph Theory course: ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH Graph Theory exercises: ruclips.net/p/PLztBpqftvzxXtYASoshtU3yEKqEmo1o1L
So glad it was helpful, thanks for watching! If you're looking for more graph theory, check out my playlist and let me know if you ever have any questions! ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
Hello! Thank you once again for your amazing videos & explanations! Here I am, struggling with two other Graph Theory problems & I was hoping you could enlighten me 😅 First one: show that a planar graph of order n > 2 ( n = number of vertices) contains no more than 3n - 6 edges. Second one: G is an undirected graph of order n. Show that 𝜒(𝐺)𝜒(𝐺̅) ≤ (𝑛 + 1)^2 / 4. ( 𝜒(𝐺) - the chromatic number of the graph, 𝜒(𝐺̅) - the chromatic number of the complement graph, n - the number of vertices). Thank you in advance, have a lovely day!
Thanks for your support, Patricia! I am glad you have found the videos helpful! Here is a proof of the first result: ruclips.net/video/3LYb3k-Huoo/видео.html As for the second result, I will add it to my list of things to do! I'd give you a hint here but I don't recognize it at first glance, would have to think about it a bit!
Thank you so much for this wonderful explanation! Graph coloring appears vague to me in lectures. Thanks to your explanation, I have a much clear idea of it and better prepare for my coming discrete mathematics final exam! 🙂
So glad it helped! Thanks for watching and check out my playlist if you're looking for more graph theory! ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
My pleasure, thanks for watching! Let me know if you ever have any video requests, and if you're looking for more graph theory - check out my playlist! ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
Hello, I have a question about the maximum k-colourable since the notes that my professor gave states that maximum k-colourable is k+1 but in your video it is only k. please enlighten me. I am reviewing for my finals exam. thank you
Always happy to get more people into his music! He can be hard to follow because he keeps changing his name. He goes by Crayon Angel now: crayonangel.bandcamp.com/track/hugging-a-ghost-2
Thanks for watching and for the request! I just recorded the edge coloring lesson, as long as there are no big problems editing - it will be up tomorrow!
My pleasure, thanks for watching and check out my graph theory playlist if you're looking for more! Let me know if you ever have any requests. ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
Please could you do a video on how to do this? For each positive integer n prove by induction that a graph G of chromatic number n contains Kn as a subgraph
I already responded to your other comment on this topic, but I'm going to comment here as well just for other viewers who may read your comment. The result is not true as stated, a graph of chromatic number n does not have to contain a Kn subgraph. Here is the lesson on the topic: ruclips.net/video/asfhdFJaGQQ/видео.html
No problem, thank you for watching! Check out my Graph Theory playlist if you're looking for more graph theory lessons, many more to come! ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
![SahBabii - Viking [Official Music Video]](http://i.ytimg.com/vi/D37cL92JX0I/mqdefault.jpg)
NOTE: At 6:30 I describe what it means for a graph to be "k-colorable". The definition I give is common, but not formal enough to avoid some possible confusion. At 7:47 I say a graph cannot be k-colorable for k greater than its number of vertices, since k colors could not be used in a coloring - there simply aren't enough vertices to accommodate k colors if k is greater than the number of vertices. However, this "upper bound" is not common in the usage of the term "k-colorable". Especially as we move on to discussing chromatic polynomials.
Often it may be convenient to say a graph is k-colorable for ANY integer greater than equal to its chromatic number. So while a complete graph on 3 vertices has chromatic number 3, for example, we could say it is k-colorable for any number greater than or equal to 3. Even though we couldn't color it with 10 distinct colors, a set of 10 colors would be sufficient (we just wouldn't use them all), so we may say it is 10-colorable anyways. Always make sure you understand the definitions being used, and I apologize if this causes any confusion!
Support the production of this course by joining Wrath of Math as a Channel Member for exclusive and early videos, original music, and upcoming lecture notes for the graph theory series! Plus your comments will be highlighted for me so it is more likely I'll answer your questions!
ruclips.net/channel/UCyEKvaxi8mt9FMc62MHcliwjoin
Graph Theory course: ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
Graph Theory exercises: ruclips.net/p/PLztBpqftvzxXtYASoshtU3yEKqEmo1o1L
Wonderful video man, thank you. Great explanations, thorough but not too dense, you are easy to understand.
So glad it was helpful, thanks for watching! If you're looking for more graph theory, check out my playlist and let me know if you ever have any questions! ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
Hi, I'm from Italy and your videos about discrete mathematics are very helpful, thank you!
Thanks for watching and I am so glad to hear they have been helpful! Let me know if you ever have any video requests!
@@WrathofMath Can you do a video about the inclusion-exclusion principle?
Hello! Thank you once again for your amazing videos & explanations! Here I am, struggling with two other Graph Theory problems & I was hoping you could enlighten me 😅
First one: show that a planar graph of order n > 2 ( n = number of vertices) contains no more than 3n - 6 edges.
Second one: G is an undirected graph of order n. Show that 𝜒(𝐺)𝜒(𝐺̅) ≤ (𝑛 + 1)^2 / 4. ( 𝜒(𝐺) - the chromatic number of the graph, 𝜒(𝐺̅) - the chromatic number of the complement graph, n - the number of vertices).
Thank you in advance, have a lovely day!
Thanks for your support, Patricia! I am glad you have found the videos helpful! Here is a proof of the first result: ruclips.net/video/3LYb3k-Huoo/видео.html
As for the second result, I will add it to my list of things to do! I'd give you a hint here but I don't recognize it at first glance, would have to think about it a bit!
@@WrathofMath Thank you so, so much! Have a good day!
Can you also give explanation for how to prove that a graph cannot be colored with less that k colors?
This is a np-complete problem, you will have to use assignment permutations and check if proper colouring is valid on given graph or not.
Thanks a lot you really explained wonderfully so easy to understand.
Awesome, thanks for watching!
Thank you so much for this wonderful explanation! Graph coloring appears vague to me in lectures. Thanks to your explanation, I have a much clear idea of it and better prepare for my coming discrete mathematics final exam! 🙂
So glad it helped! Good luck on the final!
Thank u so much! I finished my activity in 3 min after watching your vid. U the best
So glad it helped! Thanks for watching and check out my playlist if you're looking for more graph theory! ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
Thanks for the gift Sean
make a video on WAGNER theorem and line graphs
also show line graph of a cycle is a cycle
Thanks a lot ! So well explained !
My pleasure, thanks for watching! Let me know if you ever have any video requests, and if you're looking for more graph theory - check out my playlist! ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
So well explained
Very helpful 😍👍
Glad it was helpful!
good, clear explanation.thanks
i think, now im ready to my D.math final exam, ty!
Good luck!
How'd the final go?
@@PunmasterSTP i got 80 :DD
@@ZeroTwo00002 Way to go!
Hello, I have a question about the maximum k-colourable since the notes that my professor gave states that maximum k-colourable is k+1 but in your video it is only k. please enlighten me. I am reviewing for my finals exam. thank you
how about the point that dont connect to any other point? what should i color it? a different color that no point got it? or same as any point color?
Generally the idea is to use as few colors as possible, so you'd probably want to use a color you'd already used for another point.
Hello,
Do any one know answer for "Does there exist a 3-edge colourable graph with 10 vertices and 20 edges ?"
Thank you for making this
You're very welcome, thanks a lot for watching and let me know if you ever have any questions!
In the words of the great Calvin Harris, "Get some colours on!"
hi everybody, is there a video about interval graphs?
Do lecture on how to calculate the chromatic number for a graph
It would be more interesting!
Hey shawn, can i ask, what software are you using to do all of this? Is it OBS on a computer, or are you capturing on the ipad itself?
Im pretty sure it's all on his iPad which he is screen recording.
Tq for explaining it so well❣️❣️🙏
My pleasure, thanks for watching!
Hello, how many chromatic number of (c7) power 2 ????
Does someone know the outro song of this video? The musician is called vallow but i can not find the song...
Always happy to get more people into his music! He can be hard to follow because he keeps changing his name. He goes by Crayon Angel now: crayonangel.bandcamp.com/track/hugging-a-ghost-2
can you please make a video about list coloring
Thank god I found you
at time 5:45 i think you can do it with 3 colors
THANK YOU!!!😄😊
My pleasure! Thank you for watching! 😊
Please upload a video about edge colouring
Thanks for watching and for the request! I just recorded the edge coloring lesson, as long as there are no big problems editing - it will be up tomorrow!
@@WrathofMath thank you for your response
Awesome. Thanks a ton.
My pleasure, thanks for watching and check out my graph theory playlist if you're looking for more! Let me know if you ever have any requests.
ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
Could you please do a video on what is math and what are the things we can do with the help of math?
That's pretty general. Did you have anything more specific in mind?
Please could you do a video on how to do this?
For each positive integer n prove by induction that a graph G of chromatic number n contains Kn as a subgraph
I already responded to your other comment on this topic, but I'm going to comment here as well just for other viewers who may read your comment.
The result is not true as stated, a graph of chromatic number n does not have to contain a Kn subgraph. Here is the lesson on the topic: ruclips.net/video/asfhdFJaGQQ/видео.html
Thank you idol!
Thanks
Thank you so much!!!
No problem, thank you for watching! Check out my Graph Theory playlist if you're looking for more graph theory lessons, many more to come! ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
Thank u!
Glad to help!
👍👍👍👍
Thanks Andy! Many more videos on chromatic numbers and similar topics are coming, let me know if you ever have any requests!
i see orange red red
Ik1w09
I'm not 5 years old