On the number of maximal independent sets in a graph
David R. Wood
http://arxiv.org/abs/1104.1243
久々に．
頂点数nのグラフが持つ極大独立集合の数が高々3^{n/3}であるという事実は今となってはよく知られているが，これに対する短い証明を与えている．たしか，MoonとMoserの証明はshiftingのようなことをしていたけど，ここでは帰納法しか使っていない．
David R. Wood
http://arxiv.org/abs/1104.1243
久々に．
頂点数nのグラフが持つ極大独立集合の数が高々3^{n/3}であるという事実は今となってはよく知られているが，これに対する短い証明を与えている．たしか，MoonとMoserの証明はshiftingのようなことをしていたけど，ここでは帰納法しか使っていない．