A matching that covers vertices with maximum degree We have a graph G with maximum degree $\Delta$. The induced subgraph on vertices with degree equal to $\Delta$ is a bipartite graph (while the original graph is not).
Prove that G has a matching that covers all vertices with degree $\Delta$.
For example consider $K_{3,3}$ and add a vertex on one edge. So the graph has 7 vertices and 10 edges. The graph is not bipartite, but the induced subgraph on vertices with degree $\Delta(G) = 3$ is a bipartite subgraph. You can easily find a matching that covers all of the 6 vertices with degree 3.
 A: We use Tutte's theorem: if a graph $G$ with even number of vertices does not have a perfect matching, then there exists a set $S\subset V(G)$ such that the graph $G\setminus S$ has at least $|S|+2$ odd components.
Let $V=M\sqcup U$ be a vertex set, where $M$ is the set of vertices with maximal degree $\Delta$. We prove that if the induced subgraph $G(M)$ is bipartite, then
there exists a matching covering $M$. Add new set $W$,
$|W|=|M|+|U|$, of vertices to our graph, join 
them with each other and with all vertices of $U$. We have to prove that
in the new graph there exists a perfect matching. Assume the contrary,
then by the Tutte theorem there exists a set $S$ of vertices such that $G\setminus S$ has at least $|S|+2$ odd components. 
If $W\subset S$, it is a clear nonsense. Thus in $G\setminus S$ all vertices
of $(U\cup W)\setminus S$ are in the same component, hence there
exist at least $|S|+1$ odd components containing only vertices of
$M$. Consider each such odd component $K$. It is bipartite graph having, say, 
$k$ vertices in larger part and $\leq k-1$ vertices in a smaller part. 
Totally $\Delta k$ edges of $G$ go from the larger part of $K$. Between them, at most
$\Delta(k-1)$ edges go to the smaller part of $K$, hence at least $\Delta$ edges go outside $K$. 
They all go to $S$. Summing up by all odd components of $G\setminus S$ which belong to $M$ we see that at least $\Delta(|S|+1)$ edges from them come to $S$, it is impossible.
