Mixing
A proof: a bipartite graph with 2n vertices whose largest independent set size is n has a perfect matching
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
I was trying to prove the statement in the title:
Prove : A bipartite graph with 2n vertices whose largest independent set size
is n has a perfect matching.
I think I managed to solve it but I'm unsure whether or not my solution is right:
Firstly, I proved (easy to verify) that if G = ($V1 cup V2$, E) then |V1| = |V2| = n.
(*)Secondly, I proved that each vertex has at least 1 neighbour. (if there's a vertex $x$ with no neighbours in V1 then $x cup V2$ is an independent group of size n+1)
Then, I proved the statement using induction (on the size of V1). The base is simple (n=1)
Assuming that the statement is correct for a graph with |V1| = $n$. Assume G is a graph whose |V1| = n+1. If for every $S subseteq V1$, $|N(S)| >= |S|$ (where N(S) is the set of neighbours of S vertices), then by the Hall Theorem, the graph has a perfect matching.
Else, assume that there exists $S subseteq V1$ such that $|N(S)| < |S|$. According to (*) we can deduce that there exists $r in N(S)$ that has at least 2 neighbours in S, denote them x,y. (**) Note that one of them, WLOG x, has $deg(x) > 1$, because if not, then both $deg(x) = deg(y) = 1$ and then $V2 setminus r cup x,y$ is an independent group of size n+2.
So now I remove r,x from G. Denote the graph without r,x as $G'$. Note that thanks to (**), $G'$ doesn't have an independent group os size n+1. Thus, by the induction assumption, $G'$ has a perfect matching $M'$.
And now $M = M' cup x,r $ is a perfect matching in G.
I'm hoping you could tell me if this proof is indeed correct.
Thanks in advance,
Barak.
graph-theory bipartite-graph matching-theory
asked Jul 18 at 21:20
Barak B
224
add a comment |Â
up vote
1
down vote
favorite
I was trying to prove the statement in the title:
Prove : A bipartite graph with 2n vertices whose largest independent set size
is n has a perfect matching.
I think I managed to solve it but I'm unsure whether or not my solution is right:
Firstly, I proved (easy to verify) that if G = ($V1 cup V2$, E) then |V1| = |V2| = n.
(*)Secondly, I proved that each vertex has at least 1 neighbour. (if there's a vertex $x$ with no neighbours in V1 then $x cup V2$ is an independent group of size n+1)
Then, I proved the statement using induction (on the size of V1). The base is simple (n=1)
Assuming that the statement is correct for a graph with |V1| = $n$. Assume G is a graph whose |V1| = n+1. If for every $S subseteq V1$, $|N(S)| >= |S|$ (where N(S) is the set of neighbours of S vertices), then by the Hall Theorem, the graph has a perfect matching.
Else, assume that there exists $S subseteq V1$ such that $|N(S)| < |S|$. According to (*) we can deduce that there exists $r in N(S)$ that has at least 2 neighbours in S, denote them x,y. (**) Note that one of them, WLOG x, has $deg(x) > 1$, because if not, then both $deg(x) = deg(y) = 1$ and then $V2 setminus r cup x,y$ is an independent group of size n+2.
So now I remove r,x from G. Denote the graph without r,x as $G'$. Note that thanks to (**), $G'$ doesn't have an independent group os size n+1. Thus, by the induction assumption, $G'$ has a perfect matching $M'$.
And now $M = M' cup x,r $ is a perfect matching in G.
I'm hoping you could tell me if this proof is indeed correct.
Thanks in advance,
Barak.
graph-theory bipartite-graph matching-theory
asked Jul 18 at 21:20
Barak B
224
What does (**) refer to?
– Mike Earnest
Jul 18 at 21:56
Hey Mike, edited, thanks.
– Barak B
Jul 19 at 4:22
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I was trying to prove the statement in the title:
Prove : A bipartite graph with 2n vertices whose largest independent set size
is n has a perfect matching.
I think I managed to solve it but I'm unsure whether or not my solution is right:
Firstly, I proved (easy to verify) that if G = ($V1 cup V2$, E) then |V1| = |V2| = n.
(*)Secondly, I proved that each vertex has at least 1 neighbour. (if there's a vertex $x$ with no neighbours in V1 then $x cup V2$ is an independent group of size n+1)
Then, I proved the statement using induction (on the size of V1). The base is simple (n=1)
Assuming that the statement is correct for a graph with |V1| = $n$. Assume G is a graph whose |V1| = n+1. If for every $S subseteq V1$, $|N(S)| >= |S|$ (where N(S) is the set of neighbours of S vertices), then by the Hall Theorem, the graph has a perfect matching.
Else, assume that there exists $S subseteq V1$ such that $|N(S)| < |S|$. According to (*) we can deduce that there exists $r in N(S)$ that has at least 2 neighbours in S, denote them x,y. (**) Note that one of them, WLOG x, has $deg(x) > 1$, because if not, then both $deg(x) = deg(y) = 1$ and then $V2 setminus r cup x,y$ is an independent group of size n+2.
So now I remove r,x from G. Denote the graph without r,x as $G'$. Note that thanks to (**), $G'$ doesn't have an independent group os size n+1. Thus, by the induction assumption, $G'$ has a perfect matching $M'$.
And now $M = M' cup x,r $ is a perfect matching in G.
I'm hoping you could tell me if this proof is indeed correct.
Thanks in advance,
Barak.
graph-theory bipartite-graph matching-theory
asked Jul 18 at 21:20
Barak B
224
I was trying to prove the statement in the title:
Prove : A bipartite graph with 2n vertices whose largest independent set size
is n has a perfect matching.
I think I managed to solve it but I'm unsure whether or not my solution is right:
Firstly, I proved (easy to verify) that if G = ($V1 cup V2$, E) then |V1| = |V2| = n.
(*)Secondly, I proved that each vertex has at least 1 neighbour. (if there's a vertex $x$ with no neighbours in V1 then $x cup V2$ is an independent group of size n+1)
Then, I proved the statement using induction (on the size of V1). The base is simple (n=1)
Assuming that the statement is correct for a graph with |V1| = $n$. Assume G is a graph whose |V1| = n+1. If for every $S subseteq V1$, $|N(S)| >= |S|$ (where N(S) is the set of neighbours of S vertices), then by the Hall Theorem, the graph has a perfect matching.
Else, assume that there exists $S subseteq V1$ such that $|N(S)| < |S|$. According to (*) we can deduce that there exists $r in N(S)$ that has at least 2 neighbours in S, denote them x,y. (**) Note that one of them, WLOG x, has $deg(x) > 1$, because if not, then both $deg(x) = deg(y) = 1$ and then $V2 setminus r cup x,y$ is an independent group of size n+2.
So now I remove r,x from G. Denote the graph without r,x as $G'$. Note that thanks to (**), $G'$ doesn't have an independent group os size n+1. Thus, by the induction assumption, $G'$ has a perfect matching $M'$.
And now $M = M' cup x,r $ is a perfect matching in G.
I'm hoping you could tell me if this proof is indeed correct.
Thanks in advance,
Barak.
graph-theory bipartite-graph matching-theory
asked Jul 18 at 21:20
Barak B
224
edited Jul 19 at 4:21
asked Jul 18 at 21:20
Barak B
224
asked Jul 18 at 21:20
Barak B
224
asked Jul 18 at 21:20
Barak B
224
224
What does (**) refer to?
– Mike Earnest
Jul 18 at 21:56
Hey Mike, edited, thanks.
– Barak B
Jul 19 at 4:22
add a comment |Â
What does (**) refer to?
– Mike Earnest
Jul 18 at 21:56
Hey Mike, edited, thanks.
– Barak B
Jul 19 at 4:22
What does (**) refer to?
– Mike Earnest
Jul 18 at 21:56
What does (**) refer to?
– Mike Earnest
Jul 18 at 21:56
Hey Mike, edited, thanks.
– Barak B
Jul 19 at 4:22
Hey Mike, edited, thanks.
– Barak B
Jul 19 at 4:22
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
3
down vote
accepted
I think it's right, although you could simplify things a little.
Note that any bipartite graph $G=(U,V,E)$ will have an independent set at least as big as the larger of the two parts, $max(|U|,|V|)$. Thus in the given cases $|U|=|V| =n$.
Then for eliminating the case of $S subseteq U$ with $|N(S)| < |S|$, we can simply note that this would imply that the independent set $Scup (V-N(S))$ has more than $n$ vertices, which is not allowed.
This would also allow you to frame the proof without induction, since we can say:
For any subset $Ssubseteq U$, $Scup (V-N(S))$ forms an independent set. So we know that $nge |Scup (V-N(S))|=|S|+|V|-|N(S)| $ giving $|N(S)|geq|S|$ and thus Hall's marriage theorem applies.
answered Jul 18 at 21:41
Joffan
31.9k43169
Thanks, that's a nice solution actually. Though what bothered me more than the complexity of my solution, is that my teacher claimed my solution is wrong, but I couldn't find a flaw in it, and it worried me. So I'm glad you agree this is correct.
– Barak B
Jul 19 at 4:38
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
accepted
I think it's right, although you could simplify things a little.
Note that any bipartite graph $G=(U,V,E)$ will have an independent set at least as big as the larger of the two parts, $max(|U|,|V|)$. Thus in the given cases $|U|=|V| =n$.
Then for eliminating the case of $S subseteq U$ with $|N(S)| < |S|$, we can simply note that this would imply that the independent set $Scup (V-N(S))$ has more than $n$ vertices, which is not allowed.
This would also allow you to frame the proof without induction, since we can say:
For any subset $Ssubseteq U$, $Scup (V-N(S))$ forms an independent set. So we know that $nge |Scup (V-N(S))|=|S|+|V|-|N(S)| $ giving $|N(S)|geq|S|$ and thus Hall's marriage theorem applies.
answered Jul 18 at 21:41
Joffan
31.9k43169
Thanks, that's a nice solution actually. Though what bothered me more than the complexity of my solution, is that my teacher claimed my solution is wrong, but I couldn't find a flaw in it, and it worried me. So I'm glad you agree this is correct.
– Barak B
Jul 19 at 4:38
add a comment |Â
up vote
3
down vote
accepted
I think it's right, although you could simplify things a little.
Note that any bipartite graph $G=(U,V,E)$ will have an independent set at least as big as the larger of the two parts, $max(|U|,|V|)$. Thus in the given cases $|U|=|V| =n$.
Then for eliminating the case of $S subseteq U$ with $|N(S)| < |S|$, we can simply note that this would imply that the independent set $Scup (V-N(S))$ has more than $n$ vertices, which is not allowed.
This would also allow you to frame the proof without induction, since we can say:
For any subset $Ssubseteq U$, $Scup (V-N(S))$ forms an independent set. So we know that $nge |Scup (V-N(S))|=|S|+|V|-|N(S)| $ giving $|N(S)|geq|S|$ and thus Hall's marriage theorem applies.
answered Jul 18 at 21:41
Joffan
31.9k43169
Thanks, that's a nice solution actually. Though what bothered me more than the complexity of my solution, is that my teacher claimed my solution is wrong, but I couldn't find a flaw in it, and it worried me. So I'm glad you agree this is correct.
– Barak B
Jul 19 at 4:38
add a comment |Â
up vote
3
down vote
accepted
up vote
3
down vote
accepted
I think it's right, although you could simplify things a little.
Note that any bipartite graph $G=(U,V,E)$ will have an independent set at least as big as the larger of the two parts, $max(|U|,|V|)$. Thus in the given cases $|U|=|V| =n$.
Then for eliminating the case of $S subseteq U$ with $|N(S)| < |S|$, we can simply note that this would imply that the independent set $Scup (V-N(S))$ has more than $n$ vertices, which is not allowed.
This would also allow you to frame the proof without induction, since we can say:
For any subset $Ssubseteq U$, $Scup (V-N(S))$ forms an independent set. So we know that $nge |Scup (V-N(S))|=|S|+|V|-|N(S)| $ giving $|N(S)|geq|S|$ and thus Hall's marriage theorem applies.
answered Jul 18 at 21:41
Joffan
31.9k43169
I think it's right, although you could simplify things a little.
Note that any bipartite graph $G=(U,V,E)$ will have an independent set at least as big as the larger of the two parts, $max(|U|,|V|)$. Thus in the given cases $|U|=|V| =n$.
Then for eliminating the case of $S subseteq U$ with $|N(S)| < |S|$, we can simply note that this would imply that the independent set $Scup (V-N(S))$ has more than $n$ vertices, which is not allowed.
This would also allow you to frame the proof without induction, since we can say:
For any subset $Ssubseteq U$, $Scup (V-N(S))$ forms an independent set. So we know that $nge |Scup (V-N(S))|=|S|+|V|-|N(S)| $ giving $|N(S)|geq|S|$ and thus Hall's marriage theorem applies.
answered Jul 18 at 21:41
Joffan
31.9k43169
edited Jul 18 at 22:06
answered Jul 18 at 21:41
Joffan
31.9k43169
answered Jul 18 at 21:41
Joffan
31.9k43169
answered Jul 18 at 21:41
Joffan
31.9k43169
31.9k43169
Thanks, that's a nice solution actually. Though what bothered me more than the complexity of my solution, is that my teacher claimed my solution is wrong, but I couldn't find a flaw in it, and it worried me. So I'm glad you agree this is correct.
– Barak B
Jul 19 at 4:38
add a comment |Â
Thanks, that's a nice solution actually. Though what bothered me more than the complexity of my solution, is that my teacher claimed my solution is wrong, but I couldn't find a flaw in it, and it worried me. So I'm glad you agree this is correct.
– Barak B
Jul 19 at 4:38
Thanks, that's a nice solution actually. Though what bothered me more than the complexity of my solution, is that my teacher claimed my solution is wrong, but I couldn't find a flaw in it, and it worried me. So I'm glad you agree this is correct.
– Barak B
Jul 19 at 4:38
Thanks, that's a nice solution actually. Though what bothered me more than the complexity of my solution, is that my teacher claimed my solution is wrong, but I couldn't find a flaw in it, and it worried me. So I'm glad you agree this is correct.
– Barak B
Jul 19 at 4:38
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2856015%2fa-proof-a-bipartite-graph-with-2n-vertices-whose-largest-independent-set-size-i%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
What does (**) refer to?
– Mike Earnest
Jul 18 at 21:56
Hey Mike, edited, thanks.
– Barak B
Jul 19 at 4:22