co.combinatorics - Red-blue alternating paths

I think even the stronger lemma is true where all paths will be edges:

Let $G$ be a simple graph, $V_k={v_1,dots,v_k}$ a subset of vertices and we have $deg(v_i)geq i$ for all $i=1,dots,k$. Then there is a matching which covers $V_k$.

PROOF:

If there is no edge between vertices from $V_k$ (so $V_k$ is stable) then we can consider only the edges between $V_k$ and $Vsetminus V_k$ (the induced bipartite graph between $V_k$ and $Vsetminus V_k$). The degree of the vertices from $V_k$ in this bipartite graph will be the same as in the original graph, so the condition still holds. From this it follows that $V_k$ satisfies the condition of Hall's marriage theorem thus there is a matching covering $V_k$. Indeed, let $Xsubseteq V_k$, and let $v_lin X$ be the vertex with the highest index in $X$. Then $|X|leq l$. On the other hand all the neighbors of $v_l$ are in the neighborhood of $X$ so $deg(v_l)leq |N(X)|$. Combining these two observation with our condition of $deg(v_l)geq l$ we get that $|X|leq |N(X)|$

If there is an edge $(v_iv_j)$, where $v_i,v_jin V_k$, then let's choose such an edge where the sum of indexes $i+j$ is the smallest possible and suppose that $i<j$. Let's delete $v_i$ and $v_j$ from the graph. All the other vertices from $V_k$ can have their degree decrease with at most 2. If the degree of $v_l$ decreases by 1 then $v_l$ is a neighbor of $v_i$ or $v_j$ and because of $i+j$ being minimal we have $i<l$. If the degree of $v_l$ decreases by 2 then $v_l$ is a neighbor of both $v_i$ and $v_j$, and again, using that $i+j$ is minimal we have $i<j<l$. This means that by adjusting the indexes for the remaining vertices in $V_k$ in the natural way ($v_l$ remains $v_l$ if $l<i$, is renamed to $v_{l-1}$ if $i<l<j$ and is renamed to $v_{l-2}$ if $j<l$), the $V_{k-2}$ we got like this satisfies the degree condition $deg(v_i)geq i$ for all index $i$. By induction we are done in this case.

• Next co.combinatorics - Making a non-monotone function monotone
• Previous ag.algebraic geometry - Learning about Lie groups