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 (it can be decomposed into three $$$K_{1, 3}$$$'s; the three centers are $$$0$$$, $$$4$$$, and $$$5$$$). I am familiar with basic bipartite graph theorems (e.g. bipartite if and only if no odd cycle), but those don't seem to help me here either.

Can someone please help convince me that a bipartite graph check 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.