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 $$$G$$$ can be decomposed into $$$K_{1, 3}$$$ graphs if $$$G$$$ is bipartite. While this solves the problem, I'm not so sure why this is true.

I understand that each of the $$$K_{1, 3}$$$ 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 $$$3$$$," 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. I'm not so sure if my examples are valid either (the term "graph decomposition" is new to me). Here's an example that I came up with that I believe is valid:

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.