A convention of mathematicians will have rooms available in $6$ hotels. There are $n$ mathematicians and, because of personality conflicts, various pairs of mathematicians must be lodged in different hotels. The organizers wonder whether $6$ hotels will suffice to separate all conflicts. Model this conflict problem with a graph and restate the problems in terms of vertex coloring.

I am immediately confused about this question simply because I'm wondering are my vertices the hotels, the $n$ mathematicians, or the mathematicians with conflicting personalities? How could I model this using Graph Coloring?


Take your vertices to be the mathematicians, put edges bewteen two mathematicians in conflict, and choose one color per hotel.

Then the question becomes : can you color this graph such that adjacent vertices are always of different colors ?

  • $\begingroup$ How am I supposed to make a graph of $n$ vertices. Do I pick some arbitrary number? $\endgroup$ – Jodo1992 May 2 '16 at 16:19
  • 2
    $\begingroup$ The number $n$ is a parameter of the exercise. Clearly the question cannot be answered as it is (if there are more than six mathematicians and they are all crossed, six hotels won't suffice, but if actually all of them are good friends, then one is enough), it's just a modeling exercise : if I give you a list of $n$ mathematicians, you can make a graph out of this list. $\endgroup$ – Captain Lama May 2 '16 at 16:21
  • $\begingroup$ Ah I see, so I should make several graphs showing cases up to $6$ mathematicians and then show how $7$ would be an issue. $\endgroup$ – Jodo1992 May 2 '16 at 16:22
  • $\begingroup$ Well, I don't think the question asks you to actually solve the problem, but just to indicate how it can be modeled by a graph coloring. But yes, if you wanted to give a partial answer, you could explicitly construct a graph with seven vertices that shows that in general six won't be enough (which is pretty obvious). $\endgroup$ – Captain Lama May 2 '16 at 16:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.