Hi,

Today, I worked on the following problem: https://onlinejudge.org/external/113/11396.pdf (UVa 11396)

While I recognized that the problem involved bipartite graphs, I could not figure out how to solve the problem, so I looked at the answer. Accordingly, I found out that a graph

can be decomposed into

graphs if

is bipartite. While this solves the problem, I'm not so sure why this is true.

I understand that each of the

graphs can have their center vertex colored black leaving the remaining three vertices to be colored white; however, I can't really figure out where the "each vertex has degree

," and "decomposition" (the graph can have many $K_{1, 3}$'s in them) parts come into play.

I've tried drawing pictures, but I can't seem to get the intuition that a bipartite graph check is enough. It's also pretty hard for me to come up with examples in which the criteria are satisfied and a decomposition is possible. Can someone please help convince me that a bipartite graph is enough? I don't understand the intuition behind this solution, and I cannot find much reasoning online. There are hints/solutions provided here, but they do not help me very much. I would really appreciate any help.