MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

From Lovasz's Matching Theory,

Let $G$ be a bipartite graph with bipartition $(A, B)$. For $X \subset > A$, define $def(X) :=|X|-|\Gamma(X)|$, where $\Gamma(Χ)$ denote all points in $V(G)$ which are adjacent to at least one point of $X$. $def(G) := \max_{X \subset A} > def(X)$ will be called the $Α$-deficiency of $G$. If $A$ is understood, we shall simply call this number the deficiency of G.

Let $G$ be a graph not necessarily bipartite. Define $def'(X) :=odd(G-X) - |X|$, and the deficiency of the graph is defined as $def'(G) := \max_{X \subset V(G)} def'(X)$.

In a bipartite graph, these are two different concepts unfortunately with the same name in the book. From Tutte-Berge Formula, and THEOREM 1.3.1 in the book, which states

The matching number of a bipartite graph G is $|A|-def(G)$.

I derive that $def'(G) = |B| - |A| + 2 def(G).$ I wonder how to prove/explain this relation between the two deficiencies more directly based on their definitions?

Is there some definite relation between $def(X)$ and $def'(X)$ for a subset $X$ of $A$?


share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.