i'm studying for my discrete mathematics final currently, and a friend of mine from a separate section (yet same professor) gave me a possible tip on a question that may be on the final. He said "he may ask you to 'recite' the 4-color theorem as it relates to trees".
However, when we discussed the 4-color theorem in class, this is our professor gave us:
Let G be a planar graph.
Then $X(G) \le 6$
Proof: NP-complete.
So based off of the above information, I really have no idea how to apply the 4-color theorem to $anything$. Graph theory in general really confuses me, partially because we barely covered it at the end of the semester. The proof is obviously too hard for my class, so i'm not entirely sure what to study or where to begin.
I was hoping some of you could perhaps give me some examples on how the 4-color theorem may be applied to a tree graph without a proof so that I have an idea of what to study. I basically have no idea where to even start when it comes to "reciting the 4-color theorem as it relates to a tree graph".
Thank you so much in advance for those who respond as I have spent countless hours trying to understand graph theory in general and I still don't know how to apply what i've learned to paper. I also apologize if this question seems "stupid", but I feel very stupid when it comes to this stuff (and it is not for a lack of trying).
I have never seen a proof referred to as NP-complete , I'm pretty sure the intended message is more along the lines of: "$6$-coloring a planar graph has been proven to be NP complete." (Actually giving the color assignment)
The proof that every planar graph is $6$ colorable is a consequence of the $4$ color theorem. The $4$-color theorem is equivalent to every planar graph being $4$-colorable ( since the dual of the dual of a planar graph $G$ is isomorphic to $G$).