Coloring a graph with 40 vertices using only black and white

46 Views Asked by At

Consider a set of 40 houses. Each house is painted either black or white. Consider houses as vertices. Each household compares its house with the houses which are connected(adjacent) to them. In the neighborhood, if the number of houses with black color exceeds the number of white houses, depending on the color of their own house, they either keep their house black or paint it black and vice versa. This process continues. Each household compares itself with its neighbors again and again. In which step this coloring process will stop?

1

There are 1 best solutions below

0
On

My read is that
1. each household changes color to that of the majority of its neighbors.
2. Consider any graph.

If so, then when we take the cycle $C_{40}$ and color the vertices alternatively, then the coloring process will simply alternate and hence never end.