|
|
back to boardHint Posted by Mickkie 29 May 2020 00:50 This problem is easier than rating should be if you know the trick. Invariant: graph G is decomposable if and only if all the connected components of G has even number of edges. A tree is very easy to be decomposed. Creating a tree equivalent to each connected component will lead to the answer. Hope this help, Mick :) Re: Hint It helped me a lot, thank you! I read a proof of the fact that any connected graph with even number of edges is decomposable, but it was quite complicated and didn't allude at any good algorithm underneath. Your idea is much simpler and easier to proof |
|
|