Given an undirected graph $G$. Each vertex has a weight 1.
We define shrinking an edge as merging and replacing 2 adjacent vertices $(A, B)$ with a new vertex $C$ such that all the vertices that were connected to $A$ or $B$ are now connected to $C$. Moreover the weight of the new vertex $C$ is sum of weight of $A$ and $B$.
Question: Determine if for a given graph $G$, we can merge vertices such that in the new Graph:
- Each vertex has a weight 2.
- The new graph is 2 color-able.
How do we approach this problem?