그래프의 배제 번호

Question

그래프의 간선 세트 $G$두 모서리에 공통된 정점이없는 경우 일치합니다. 짝수 정수$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}$ 하나를 제외한 모든 정점을 포함하는 모서리 $G$. 세트$F$ 가장자리의 $G$ 다음과 같은 경우 배제 집합이라고합니다. $G-F$완벽하고 홀수 완벽하게 일치하지 않습니다. 일치하는 배제 번호$G$, $mp(G)$, 최소 배제 세트의 크기입니다.

내 질문은 다음과 같습니다.

만약 $G$ 순서가 균등 한 그래프 $n$, 그렇다면 왜 $mp(G)\leq \delta(G)$?

내가 시도한 것 : Let $v$ 꼭지점이있다 $\deg (v)=\delta(G)$. 허락하다$F$ 정점에 입사하는 모든 모서리의 집합 $v$. 나는 그것을 보여주고 싶다$G-F$완전 (또는 홀수 완전 일치)이 없습니다. 만약$G-F$ 일치하는 경우 $v(G-F)=even$ 그 후 $v(G)=odd$그것은 모순입니다. 하지만 보여줄 줄 몰라$G-F$ 이상하고 완벽한 매칭이 없습니다.

미리 감사드립니다.

Answer 1

복용에 대한 당신의 생각 $F$ 가장자리와 함께 $v$맞다. 이후$v$ 그것에 입사하는 가장자리가 없습니다 $G-F$, 이상한 완벽한 일치를 찾는 $G-F$ 완벽한 매칭을 찾는 것과 같습니다. $G-v$ (당신이 가지고 있어야하기 때문에 $v$타의 추종을 불허하는 꼭지점으로). 그러나 이것은 불가능합니다.$G-v$ 홀수의 정점이 있습니다.

편집 : 더 쉬울 수있는 또 다른 생각은 그래프가 $n$ 홀수를 가진 그래프를 보여주는 거의 동일한 패리티 인수에 의해 홀수 완전 매칭이 전혀 없습니다. $n$ 완벽한 매칭은 없습니다.

Answer 2

나는 언제 $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)$.