# Merging Graph Edges to form a 2 color-able Graph (with weight constraints)?

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:

1. Each vertex has a weight 2.
2. The new graph is 2 color-able.

How do we approach this problem?

• Thank you. If each vertex has a constraint that its degree is $>=2$ is the problem still NP Complete? May 28 '17 at 10:01
• Sure. If any vertex has degree $0$ then the answer is trivially no, so we don't need to consider that case. If some vertex $v$ has degree $1$ then we can add two vertices $u_1$ and $u_2$ and three edges $(v, u_1)$, $(v, u_2)$, and $(u_1, u_2)$ without changing the answer to the problem. This works because every perfect matching in the resulting graph includes edge $(u_1, u_2)$. Notice that applying this transformation for every degree-$1$ vertex increases the minimum degree to $2$. May 28 '17 at 11:27