Given a undirect graph G=(N, E) a two colour scheme assigns to each node either the colour black or white. A node is diverse if it has the opposite colour of at least half of its neighbours. How can you assign a diverse colour to all the nodes in a graph?
tricky one
Posts
25 minutes ago
1. Colour the nodes in any way you want. Could be, e.g., all white.
ReplyDelete2. As long as you see a node that is not diverse, change its colour to the opposite.
This will end at some point because, every time you do step 2, you strictly decrease the number of edges connecting nodes of the same colour. There's only a finite number of them, so this gives an upper bound on the number of steps.