より高い次数の場合

ウィキペディア小見出し辞書

より高い次数の場合

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/01/20 05:15 UTC 版)

「ピーターセンの定理」の記事における「より高い次数の場合」の解説

d 次の正則グラフ G の辺連結度が d − 1 以上で、かつ G の頂点数が偶数であれば、完全マッチングが存在する。このときさらに、G の任意の辺に対しそれを含むような完全マッチングが存在することが言える（なお次数 d が奇数のときは握手補題（英語版） （handshaking lemma）より頂点数は必ず偶数になるから、これを仮定する必要はなくなる）。