Editorial for Mock CCC '21 S5 - Clique and Independent Set
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Imagine that the graph is complete and each edge is either red or blue, and now we wish to count the number of ways to 2-color the graph such that the red and blue vertices are cliques if you look at the red and blue edges respectively.
Let be the number of red edges incident on . If is red, then we can prove that all nodes with must also be red. This gives an solution.
Note that this means the problem is solvable with only the degrees of the nodes - the actual graph is irrelevant otherwise.
Comments