Using graph theory to find the maximum compatible clique

Question

Imagine a person wants to celebrate his birthday. But some of the guests don't like each other.

Person A says she won't come if Person B or Person C is there. Person B and Person D say that they won't come if Person E is there. Person E wont come if Person F is there. Person F always argues with Person D.

Actually the Birthday child don't like his Friends, but he wants to invite them anyway.

Question: How often does he have to invite at least to the birthday, so there is no dispute.

My work:

As you can read in the title I really want to solve this with graph theory. I draw a directed graph. I have 6 nodes. I draw an Edge whenever a person doesn't like another person. But how can graph theory help me here? Maybe matching in term of graph theory can help us?

Answer 1

Here is the complete graph showing what happens if everyone is invited:

Now delete the incompatible links

Now look for the maximum complete subgraphs: They are $\{ B, C, D \}$ and $\{ B, C, F \}$.

So the largest party has three people: $B$ and $C$ with either $D$ or $F$.

---

In Mathematica:

g = CompleteGraph[6,
  VertexLabels -> 
   Rule @@@ Transpose[{Range[6], CharacterRange["A", "F"]}]];

h = EdgeDelete[g, 
 {1 <-> 2, 1 <-> 3, 2 <-> 5, 4 <-> 5, 5 <-> 6, 4 <-> 6}];

Select[
    Subgraph[h, #, 
    VertexLabels -> 
     Rule @@@ Transpose[{Range[6], CharacterRange["A", "F"]}]] & /@ 
  Subsets[Range[6], {3}], CompleteGraphQ]