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.

  • 6
    $\begingroup$ "Prove that ...": why do you know the assertion is true? -- Is this an exercise? $\endgroup$ – Stefan Kohl Oct 3 '15 at 19:29
  • 2
    $\begingroup$ duplicate of math.stackexchange.com/questions/638598/… $\endgroup$ – Chris Godsil Oct 3 '15 at 23:08
  • 4
    $\begingroup$ @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! $\endgroup$ – Mohemnist Oct 4 '15 at 12:35
  • 1
    $\begingroup$ 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! $\endgroup$ – Mohemnist Oct 4 '15 at 12:43
  • 1
    $\begingroup$ @BenBarber Please check my comment for you answer. $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ Very nice argument! I added more details, but then decided it was better the way it was before. $\endgroup$ – Tony Huynh Oct 4 '15 at 23:29
  • $\begingroup$ 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$. $\endgroup$ – Mohemnist Oct 5 '15 at 7:01
  • $\begingroup$ If graph has even number of vertices, then $o(G\setminus S)+|S|$ is always even. $\endgroup$ – Fedor Petrov Oct 5 '15 at 7:12
  • $\begingroup$ @FedorPetrov Yes, You are right. What about the situation when two parts have the same number of vertices $k$? $\endgroup$ – Mohemnist Oct 5 '15 at 8:40
  • 1
    $\begingroup$ Then it is not very much odd, right? $\endgroup$ – Fedor Petrov Oct 5 '15 at 8:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.