對每個葉子結(jié)點(diǎn),它只能和唯一與它相鄰的那個點(diǎn)匹配
如果一個結(jié)點(diǎn)連了兩個或以上的葉子結(jié)點(diǎn),那么這兩個葉子結(jié)點(diǎn)中至少有一個是不能匹配的
所以,只有當(dāng)每個結(jié)點(diǎn)最多只和一個葉子結(jié)點(diǎn)相鄰的時候,才會存在完美匹配
去掉葉子結(jié)點(diǎn)以及與其相鄰的點(diǎn),會得到若干不連通的樹
重復(fù)上面的過程,直到所有的結(jié)點(diǎn)都被匹配或者有點(diǎn)不能被匹配
由于在任意階段,每個結(jié)點(diǎn)最多只會和一個葉子結(jié)點(diǎn)相連,所以這個匹配的方法都是被唯一確定下來的
因此一棵樹最多只有一種完美匹配的方法.