# 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.

• "Prove that ...": why do you know the assertion is true? -- Is this an exercise? – Stefan Kohl Oct 3 '15 at 19:29
• duplicate of math.stackexchange.com/questions/638598/… – Chris Godsil Oct 3 '15 at 23:08
• @StefanKohl Yes and No! It was an exercise of a graduate course, but I wasn't solve by the students in the time, and the teacher doesn't seem to know the answer and asked the student to search for it! – Mohemnist Oct 4 '15 at 12:35
• ChrisGodsil and @BenBarber The question is more general and the proposed solution for that, doesn't work for the example that I mentioned above ($K_{3,3}+v$). As TonyHuynh mentioned, a vertex (v in the example) can be in both matchings and produce a path of length even (in the example) two, in this case the matching cannot be corrected. One of my ideas was to remove the corrupted matching (find and remove a subgraph $H$ of $G$ that each vertex with maximum degree in $G$ has degree 1 in $H$ and other vertices have degree 0,1 or 2) and reduce the $\Delta$ by one and use induction afterward! – Mohemnist Oct 4 '15 at 12:43
• @BenBarber Please check my comment for you answer. – Mohemnist Oct 5 '15 at 9:57

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.

• Very nice argument! I added more details, but then decided it was better the way it was before. – Tony Huynh Oct 4 '15 at 23:29
• The Tutte's condition is $\forall S \subseteq V, o(G\backslash S)\le|S|$, so the reverse is $\exists S \subseteq V, o(G\backslash S) > |S|$ or $o(G\backslash S) \ge |S|+1$, not $o(G\backslash S) \ge |S|+2$. – Mohemnist Oct 5 '15 at 7:01
• If graph has even number of vertices, then $o(G\setminus S)+|S|$ is always even. – Fedor Petrov Oct 5 '15 at 7:12
• @FedorPetrov Yes, You are right. What about the situation when two parts have the same number of vertices $k$? – Mohemnist Oct 5 '15 at 8:40
• Then it is not very much odd, right? – Fedor Petrov Oct 5 '15 at 8:58