Auf der Ausschlussnummer eines Graphen

Question

Eine Reihe von Kanten in einem Diagramm $G$ist eine Übereinstimmung, wenn keine zwei Kanten einen gemeinsamen Scheitelpunkt haben. Für eine gerade ganze Zahl$n$, ein $n$-Vertex-Diagramm $G$ hat eine perfekte Übereinstimmung, wenn es gibt $\frac{n}{2}$ Kanten $x_1 y_1 ,x_2 y_2, \ldots ,x_{\frac{n}{2}}y_{\frac{n}{2}}$ mit allen Eckpunkten von $G$. Wenn$n$ ist ungerade, $G$ hat eine ungerade-perfekte Übereinstimmung, wenn es gibt $\frac{(n-1)}{2}$ solche Kanten, an denen alle bis auf einen der Eckpunkte von beteiligt sind $G$. Ein Set$F$ von Kanten von $G$ wird als Ausschlussmenge bezeichnet, wenn $G-F$hat keine perfekte und ungerade-perfekte Übereinstimmung. Die übereinstimmende Ausschlussnummer von$G$, $mp(G)$ist die Größe eines minimalen Ausschlusssatzes.

Meine Frage ist:

Wenn $G$ eine Grafik mit gleichmäßiger Reihenfolge $n$, warum dann $mp(G)\leq \delta(G)$?

Was ich versucht habe: Lass $v$ sei ein Scheitelpunkt mit $\deg (v)=\delta(G)$. Lassen$F$ sei die Menge aller mit dem Scheitelpunkt einfallenden Kanten $v$. Das möchte ich zeigen$G-F$hat keine perfekte (oder ungerade-perfekte Übereinstimmung). Wenn$G-F$ hat dann eine Übereinstimmung $v(G-F)=even$ daher $v(G)=odd$Das ist ein Widerspruch. Aber ich weiß nicht, wie ich es zeigen soll$G-F$ hos keine ungerade-perfekte Übereinstimmung.

Danke im Voraus.

Answer 1

Ihre Idee zu nehmen $F$ die Kanten sein, die mit einfallen $v$ist richtig. Schon seit$v$ hat keine Kanten damit in $G-F$und finden eine seltsame perfekte Übereinstimmung in $G-F$ ist gleichbedeutend mit der Suche nach einer perfekten Übereinstimmung in $G-v$ (da musst du haben $v$als Ihr unübertroffener Scheitelpunkt). Dies ist aber nicht möglich, da$G-v$ hat eine ungerade Anzahl von Eckpunkten.

BEARBEITEN: Eine andere Art, darüber nachzudenken, die möglicherweise einfacher ist, ist nur, dass ein Diagramm mit $n$ gerade hat nie eine ungerade perfekte Übereinstimmung, bei weitem das gleiche Paritätsargument, das ein Diagramm mit ungeraden zeigt $n$ hat nie eine perfekte Übereinstimmung.

Answer 2

Ich denke wann $n$ ist gerade, müssen wir nehmen $F$ Die Menge aller mit dem Scheitelpunkt einfallenden Kanten $v$. Dann gibt es keine Kante in$G-F$ Vorfall zu $v$daher gibt es keine perfekte Übereinstimmung. Deshalb$mp(G)\leq \delta(G)$. Aber wenn$n$ ist seltsam, das ist überhaupt nicht der Fall, weil nach der Definition von $F$, $G-F$ kann eine ungerade-perfekte Übereinstimmung haben (es ist nicht erforderlich, dass eine Kante einfällt $v$per Definition von ungerade-perfektem Matching). Zum Beispiel können wir einen Pfad mit 5 Eckpunkten mit Start betrachten$v=v_1$. Wenn wir die Kante entfernen$v_1 v_2$, dann ist der verbleibende Graph eine ungerade-perfekte Übereinstimmung (dh $mp(G)\not \leq \delta(G)$). Ich denke in diesem Fall müssen wir nehmen$F$ Die Menge aller mit dem Scheitelpunkt einfallenden Kanten $v$ oder $w$, wo $w$ ist ein Scheitelpunkt mit $\delta(G)\leq \deg (w)$ und $\deg(w)\leq$alle anderen Grade. Dann$mp(G)\leq \delta(G)+deg(w)$.