Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$?

Thanks!

share|improve this question
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.