グラフの除外番号について
グラフのエッジのセット $G$2つのエッジに共通の頂点がない場合のマッチングです。偶数の場合$n$、 $n$-頂点グラフ $G$ ある場合は完全に一致します $\frac{n}{2}$ エッジ $x_1 y_1 ,x_2 y_2, \ldots ,x_{\frac{n}{2}}y_{\frac{n}{2}}$ のすべての頂点を含む $G$。場合$n$ 奇妙です、 $G$ ある場合は奇数完全一致があります $\frac{(n-1)}{2}$ 1つを除くすべての頂点を含むそのようなエッジ $G$。セット$F$ のエッジの $G$ 次の場合、除外セットと呼ばれます $G-F$完全なマッチングと奇妙な完全なマッチングはありません。の一致する除外番号$G$、 $mp(G)$、は最小除外セットのサイズです。
私の質問はそれです：
場合 $G$ 偶数次のグラフ $n$、 それでなんで $mp(G)\leq \delta(G)$？
私が試したこと： $v$ 頂点になる $\deg (v)=\delta(G)$。しましょう$F$ 頂点に入射するすべてのエッジのセットである $v$。それを見せたい$G-F$完全な（または奇数完全なマッチング）はありません。場合$G-F$ 一致する場合は $v(G-F)=even$ したがって、 $v(G)=odd$これは矛盾です。でも見せ方がわからない$G-F$ 奇妙な完璧なマッチングはありません。
前もって感謝します。
回答
取るというあなたの考え $F$ に付随するエッジになる $v$正しい。以来$v$ にエッジが入射していません $G-F$、で奇妙な完全一致を見つける $G-F$ で完全に一致するものを見つけることと同等です $G-v$ （あなたが持っている必要があるので $v$一致しない頂点として）。しかし、これは不可能です。$G-v$ 頂点の数が奇数です。
編集：それについてもっと簡単かもしれない別の考え方は、 $n$ 奇数のグラフを表示するのとほぼ同じパリティ引数によって、奇数の完全一致が発生することはありません。 $n$ 完全に一致することはありません。
私はいつ $n$ でも、取る必要があります $F$ 頂点に入射するすべてのエッジのセット $v$。その後、エッジはありません$G-F$ に事件 $v$したがって、完全に一致するものはありません。したがって、$mp(G)\leq \delta(G)$。でもいつ$n$ 奇妙なことですが、そうではありません。 $F$、 $G-F$ 奇数完全一致を持つことができます（エッジをに入射させる必要はありません） $v$奇数完全マッチングの定義による）。たとえば、開始時に5つの頂点を持つパスを検討できます。$v=v_1$。エッジを削除すると$v_1 v_2$、残りのグラフは奇数完全一致です（つまり $mp(G)\not \leq \delta(G)$）。この場合、私たちは取る必要があると思います$F$ 頂点に入射するすべてのエッジのセット $v$ または $w$、 どこ $w$ の頂点です $\delta(G)\leq \deg (w)$ そして $\deg(w)\leq$その他の学位。次に$mp(G)\leq \delta(G)+deg(w)$。