La desigualdad en grados implica perfecto maridaje

Question

Deje $G$ ser un bipartito gráfico con desdoblamiento $(X, Y)$ tal que $\delta(v)\geq 1$ por cada $v\in V(G)$ y siempre que $xy$ es un borde de $G$,$x\in X$$y\in Y$,$\delta(x)\geq\delta(y)$. Demostrar que no es una coincidencia que satura $X$.

He tratado de Salón de uso del teorema; uno fácilmente se puede reducir este problema, mostrando que bajo las mismas condiciones, $|X|\leq |Y|$. Sin embargo no he sido capaz de hacer esto. Alguna ayuda?

Answer 1

Asignar un peso de $w(xy):=\frac1{\delta(y)}$ a cada arista $xy$. A continuación, el peso total es de $$\sum_{xy\in E}w(xy)=\sum_{y\in Y}\sum_{x\in Nb(y)}w(xy)= \sum_{y\in Y}\sum_{x\in Nb(y)}\frac1{\delta(y)}=\sum_{y\in Y}1=|Y|.$$ Pero también es $$\sum_{xy\in E}w(xy)=\sum_{x\in X}\sum_{y\in Nb(x)}w(xy)= \sum_{x\in X}\sum_{y\in Nb(x)}\frac1{\delta(y)}\ge \sum_{x\in X}\sum_{y\in Nb(x)}\frac1{\delta(x)}=\sum_{x\in X}1=|X|.$$ Por lo tanto $$|X|\le |Y|.$$