[TECH] On The Uniqueness Of a Perfect Match In Undirected Acyclic graphs.

I was studying about several results related to Tiling Theory. Tiling Theory adds formalism to the question " Given a simple rectangular region (R) can we find a valid tiling by using tiles from a set (T) ". If our tile set (T) is a singleton set with a unit square then we can tile any region. However what if the the tile set contains only a 2x1 rectangle (domino)? what if the tile set contains a set of polymino's (tetris game)?. Although the question may seem very simple there is a rich combinatorial work based on this question. In fact the study about the tiling problem originated from Wang's Conjecture about periodic tiling. Actually the algorithmic research about tiling theory was dormant for quite some time, even the proof for 2x1 dominoes is fairly recent see this . I was reading about the proof and was really impressed by its elegance. Often people consider simple things useless or don't have enough respect for simple facts, however I always find that good results are based on several very simple facts. In fact I would like to highlight simple ideas in every algorithm I study about.

In this proof to prove that the problem is NP-complete for 2x1 domino's a simple fact that " There is exactly only one perfect matching (if at all one exists) in a Tree " is used. This can be proved intuitively as follows.

Let M be the perfect match in the Tree T, if M is not a unique perfect match then there should be some other perfect match lets call it M^'. If we observe the leaf nodes in T which have only one edge adjacent on them so both M and M^' should agree on the matched edges which have leaf nodes of T as the vertices . We can now delete all the leaf nodes and their adjacent edges and continue the argument until we don't have any leaf nodes. Thus from this argument its clear that both M and M^' are the same and hence there is only a unique perfect match if at all if one exists in a tree T.