Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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

Assuming I have a bipartite graph with the following property:

for each subgroup of nodes $s \subseteq {V} $ :

$$ \sum_{v\epsilon N(S),z\epsilon N(N(S)) }{} {(v,z) \geq 2\left \| S \right \|} $$

Where $N(S)$ is the neighbourhood of $A$.

i.e. if you go over each of $S$ neighbors and count the edges coming out from each one. the number of edges is grater than or equal to twice the size of the subgroup S.

How can I show that this graph has a double matching, where double matching is a graph with 2 different perfect matching.

I know it is true by intuition but I can't seem to find a way to prove it formally.


I tried to use Hall's theorem, but it doesn't seem to be correct, because I am counting the number of edges and as a result I am not getting the size of the |N(S)|, because some of the vertices counted more than once.

assuming I have the graph $V= \{v_1, v_2 , u_1, u_2\}$. and $v_1$ is connected to $u_1$ and $u_2$, and $v_2$ is connected to $u_1$ and $u_2$. this graph has the property I mentioned above, and it's pretty obvious that there is a double matching in here.

But if you look at the size of the neighborhood of $S=\{v_1, v_2\}$, it will be $|{u1,u2}| = 2$

and not $2|S|= 4$ as Hall's theorem requires (because when you are counting the vertices you count $u_1$ and $u_2$ twice. once as $v_1$1 neighbors, and once as $v_2$ neighbors).

Also if I try to use Hall's theorem I nned to 1. choose a first perfect matching 2. remove it, and see that there is still a perfect matching (i.e. the is a double matching)

but in this case we can choose a perfect matching that will leave us without a choice for the second matching.

Please advice..

share|cite|improve this question
up vote 4 down vote accepted


Ok, I was wrong, I think that your conjecture is false. As mentioned in comments, I assume the following property

$$\sum_{v\in N(S),\ z\in N(N(S)) }(v,z) \geq 2 |S| \tag{$\spadesuit$}$$

Consider the following bipartite graph (obviously it doesn't even have a single matching):


Let $S_\bullet$ be the part of $S$ that contains black vertices, and $S_\circ$ the rest. If $S_\bullet$ is not empty, then sum contains at least all the blue edges, hence $8 \geq 2 |S_\bullet|$. Also, if $S_\circ$ contains any of the first two white vertices, then again $8 \geq 2 |S_\circ|$ because of the blue edges. Moreover, if $S_\circ$ does not contain any of the first two white vertices, then $4 \geq 2 |S_\circ|$. Finally, because of how the left-hand side sum is stated, the blue edges induces by $S_\circ$ and $S_\bullet$ will be counted appropriate number of times, that is one for $v \in N(S_\bullet)$ and one for $v \in N(S_\circ)$, hence, condition $(\spadesuit)$ is satisfied.

I hope this helps now ;-)

share|cite|improve this answer
This is exactly what I tried to do, but I don't think this is correct. Hall's theroem is reffering to vertexes and here I am counting the number of edges. – user844541 Jul 14 '13 at 9:19
I changed my question, can you see my edit? – user844541 Jul 14 '13 at 9:34
@user844541 I don't have time right now, I will look at your question in more detail later. Just to let you know, I thought that in your notation $\|S\|$ also includes vertices, because if it doesn't, then a graph with no edges satisfies your property, i.e. $0 \geq 2\cdot 0$. – dtldarek Jul 14 '13 at 10:25
@user844541 The basic problem with condition $\spadesuit$ is that it counts somebody's else edges, for example it does not enforce that a vertex has to have more than one edge (even with counting edges once, you could make the graph similar to mine with $\Theta(n^2)$ blue edges). Moreover, besides number of edges, you would need that these edges spread is good (among others, there's no situation analogous to the two red edges). My intuition thinks that there are many possible ways to fix it, but those could be summed up to: make the condition more Hall's-theorem-like. – dtldarek Jul 15 '13 at 7:47
@user844541 They heavily depend on the fact that the matrix is doubly stochastic. In other words, sum of any row is $1$, therefore sum of $k$ rows is $k$, that is, $\sum_{v \in A,\ w \in N(A)} \omega(v,w) = |A|$. Your line does the same for columns, i.e. sum of any column is $1$, hence any $k$ columns sum up to $k$. The inequality $|N(A)| \geq |A|$ comes from the fact that $N(A)$ contains all non-zero terms of rows of $A$. – dtldarek Jul 15 '13 at 9:09

Your Answer


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

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