Given an undirected unweighted graph consisting of n vertices and m edges. we have to write a number on each vertex of the graph. Each number should be 1 , 2 or 3. The graph becomes beautiful if for each edge the sum of numbers on vertices connected by this edge is odd. Calculate the number of possible ways to write numbers 1 , 2 and 3 on vertices so the graph becomes beautiful. we have to write exactly one number on each vertex. The graph does not have any self-loops or multiple edges.
If we denote a way to distribute numbers as a painting and call the paintings that meet the constraints good paintings (and all other paintings are bad).
We can solve the problem for each connected component of the graph independently and multiply the answers. If we analyze a painting of some connected component. If some vertex has an odd number written on it, then we should write even numbers on all adjacent vertices, and vice versa. So in fact we need to check if the component is bipartite, and if it is, divide it into two parts.
How to prove that number of good paintings is $2^{a} +2^{b}$,where a is the size of the first part, and b is the size of the second part?
we write 2's into all vertices of one part, and 1's or 3's into all vertices of another part.For each 2 there are two choices $1$ or $3$ so number of ways is $2^a$,how do we get $2^b$?