The question appears in Cormen's Introduction to Algorithms.There are two types of professional wrestlers: babyfaces(good guys) and heels(bad guys). Between any pair of professional wrestlers, there may or may not be a rivalry. Suppose we have n professional wrestlers and we have a list of r pairs of wrestlers for which there are rivalries. Give an O(n+r)-time algorithm that determines whether it is possible to designate some of the wrestlers as babyfaces and the remainder as heels such that each rivalry is between a babyface and a heel. If it is possible to perform such a designation, your algorithm should produce it. One of the solutions I found said the following -Create a graph G where each vertex represents a wrestler and each edge represents a rivalry. The graph will contain n vertices and r edges. Perform as many BFS's as needed to visit all vertices. Assign all wrestlers whose distance is even to be good guys and all wrestlers whose distance is odd to be bad guys. Then check each edge to verify that it goes between a good guy and a bad guy. This solution would take O(n + r) time for the BFS, O(n) time to designate each wrestler as a good guy or bad guy, and O(r) time to check edges, which is O(n + r) time overall.Sure this solution works in all the cases I could come up with, and determines whether it is possible to color the graph in this manner or not. But I wish to know how do we formally verify the correctness of this solution? That is to say that, how do we determine if this solution exhausts all possible ways of coloring a graph in the manner asked of in the question, so as to declare whether or not it is possible to divide the graph in such a way. 
Two color Graph Coloring problem with solution involving BFS
graph theory