Mixing
Bipartite Graphs-Neighborhood Size
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
A bipartite graph $G(U,V)$ with two vertex partitions $U$ and $V$, and two subsets of $U$, $U_1$ and $U_2$, prove
$$|N(U_1)|+|N(U_2)|≥|N(U_1∪U_2)|+|N(U_1∩U_2)|$$
I can only prove equal. How to prove greater than?
graph-theory
asked Jul 22 at 7:35
Fatemath
62
add a comment |Â
up vote
1
down vote
favorite
A bipartite graph $G(U,V)$ with two vertex partitions $U$ and $V$, and two subsets of $U$, $U_1$ and $U_2$, prove
$$|N(U_1)|+|N(U_2)|≥|N(U_1∪U_2)|+|N(U_1∩U_2)|$$
I can only prove equal. How to prove greater than?
graph-theory
asked Jul 22 at 7:35
Fatemath
62
for each vertex in $V$ think about which of the four sets can it belong to.
– Roronoa Zoro
Jul 22 at 7:39
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
A bipartite graph $G(U,V)$ with two vertex partitions $U$ and $V$, and two subsets of $U$, $U_1$ and $U_2$, prove
$$|N(U_1)|+|N(U_2)|≥|N(U_1∪U_2)|+|N(U_1∩U_2)|$$
I can only prove equal. How to prove greater than?
graph-theory
asked Jul 22 at 7:35
Fatemath
62
A bipartite graph $G(U,V)$ with two vertex partitions $U$ and $V$, and two subsets of $U$, $U_1$ and $U_2$, prove
$$|N(U_1)|+|N(U_2)|≥|N(U_1∪U_2)|+|N(U_1∩U_2)|$$
I can only prove equal. How to prove greater than?
graph-theory
asked Jul 22 at 7:35
Fatemath
62
edited Jul 23 at 4:01
asked Jul 22 at 7:35
Fatemath
62
asked Jul 22 at 7:35
Fatemath
62
asked Jul 22 at 7:35
Fatemath
62
62
for each vertex in $V$ think about which of the four sets can it belong to.
– Roronoa Zoro
Jul 22 at 7:39
add a comment |Â
for each vertex in $V$ think about which of the four sets can it belong to.
– Roronoa Zoro
Jul 22 at 7:39
for each vertex in $V$ think about which of the four sets can it belong to.
– Roronoa Zoro
Jul 22 at 7:39
for each vertex in $V$ think about which of the four sets can it belong to.
– Roronoa Zoro
Jul 22 at 7:39
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
1
down vote
Wait, hang on.
I can only prove equal. How to prove greater than?
If someone asks you to prove $A ge B$, and you managed to prove $A = B$, you're done! You proved more than was asked of you, not less. You don't need to also "prove greater than". If they are equal, they are equal.
What you should be worried about when that happens is, why were you asked to only prove $A ge B$ when in fact $A = B$? Either whoever asked you the question was satisfied with you proving just the weaker statement for some reason, or your proof is incorrect.
In this case, I'm afraid your proof is incorrect.
Take the bipartite graph on $V = 1,2 cup a,b$ with edges $1,a,1,b,2,b$ and let $U_1 = 1$ and $U_2=2$. You have $|N(U_1)|=2,|N(U_2)|=1,|N(U_1 cup U_2)|=2$ and $|N(U_1 cap U_2)|=0$. So $2+1 ge 2+0$ holds as an inequality, not an equality.
Go over your proof-of-equality carefully, and see where the error is. In all likelihood your argument will let you show the inequality.
answered Jul 22 at 8:36
Alon Amit
10.2k3765
add a comment |Â
up vote
0
down vote
Consider four set of vertices from $V$, defined as follows:
- $V_1 = N(U_1 cap U_2)$, vertices connected to the vertices common to $U_1$ and $U_2$
- $V_2 = (N(U_1)cap N(U_2))backslash V_1$, the vertices other than $V_1$ connected to both $U_1$ and $U_2$
- $V_3 = N(U_1)backslash (V_1cup V_2)$, vertices connected to $U_1$ but not $U_2$
- $V_4 = N(U_2)backslash (V_1cup V_2)$, vertices connected to $U_2$ but not $U_1$
Then
- $|N(U_1)|=|V_1|+|V_2|+|V_3|,$
- $|N(U_2)|=|V_1|+|V_2|+|V_4|,$
- $|N(U_1cup U_2)|=|V_1|+|V_2|+|V_3|+|V_4|,$ and
- $|N(U_1cap U_2)|=|V_1|$
and the inequality follows, of size $|V_2|$.
answered Jul 22 at 15:48
Joffan
31.8k43169
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
Wait, hang on.
I can only prove equal. How to prove greater than?
If someone asks you to prove $A ge B$, and you managed to prove $A = B$, you're done! You proved more than was asked of you, not less. You don't need to also "prove greater than". If they are equal, they are equal.
What you should be worried about when that happens is, why were you asked to only prove $A ge B$ when in fact $A = B$? Either whoever asked you the question was satisfied with you proving just the weaker statement for some reason, or your proof is incorrect.
In this case, I'm afraid your proof is incorrect.
Take the bipartite graph on $V = 1,2 cup a,b$ with edges $1,a,1,b,2,b$ and let $U_1 = 1$ and $U_2=2$. You have $|N(U_1)|=2,|N(U_2)|=1,|N(U_1 cup U_2)|=2$ and $|N(U_1 cap U_2)|=0$. So $2+1 ge 2+0$ holds as an inequality, not an equality.
Go over your proof-of-equality carefully, and see where the error is. In all likelihood your argument will let you show the inequality.
answered Jul 22 at 8:36
Alon Amit
10.2k3765
add a comment |Â
up vote
1
down vote
Wait, hang on.
I can only prove equal. How to prove greater than?
If someone asks you to prove $A ge B$, and you managed to prove $A = B$, you're done! You proved more than was asked of you, not less. You don't need to also "prove greater than". If they are equal, they are equal.
What you should be worried about when that happens is, why were you asked to only prove $A ge B$ when in fact $A = B$? Either whoever asked you the question was satisfied with you proving just the weaker statement for some reason, or your proof is incorrect.
In this case, I'm afraid your proof is incorrect.
Take the bipartite graph on $V = 1,2 cup a,b$ with edges $1,a,1,b,2,b$ and let $U_1 = 1$ and $U_2=2$. You have $|N(U_1)|=2,|N(U_2)|=1,|N(U_1 cup U_2)|=2$ and $|N(U_1 cap U_2)|=0$. So $2+1 ge 2+0$ holds as an inequality, not an equality.
Go over your proof-of-equality carefully, and see where the error is. In all likelihood your argument will let you show the inequality.
answered Jul 22 at 8:36
Alon Amit
10.2k3765
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Wait, hang on.
I can only prove equal. How to prove greater than?
If someone asks you to prove $A ge B$, and you managed to prove $A = B$, you're done! You proved more than was asked of you, not less. You don't need to also "prove greater than". If they are equal, they are equal.
What you should be worried about when that happens is, why were you asked to only prove $A ge B$ when in fact $A = B$? Either whoever asked you the question was satisfied with you proving just the weaker statement for some reason, or your proof is incorrect.
In this case, I'm afraid your proof is incorrect.
Take the bipartite graph on $V = 1,2 cup a,b$ with edges $1,a,1,b,2,b$ and let $U_1 = 1$ and $U_2=2$. You have $|N(U_1)|=2,|N(U_2)|=1,|N(U_1 cup U_2)|=2$ and $|N(U_1 cap U_2)|=0$. So $2+1 ge 2+0$ holds as an inequality, not an equality.
Go over your proof-of-equality carefully, and see where the error is. In all likelihood your argument will let you show the inequality.
answered Jul 22 at 8:36
Alon Amit
10.2k3765
Wait, hang on.
I can only prove equal. How to prove greater than?
If someone asks you to prove $A ge B$, and you managed to prove $A = B$, you're done! You proved more than was asked of you, not less. You don't need to also "prove greater than". If they are equal, they are equal.
What you should be worried about when that happens is, why were you asked to only prove $A ge B$ when in fact $A = B$? Either whoever asked you the question was satisfied with you proving just the weaker statement for some reason, or your proof is incorrect.
In this case, I'm afraid your proof is incorrect.
Take the bipartite graph on $V = 1,2 cup a,b$ with edges $1,a,1,b,2,b$ and let $U_1 = 1$ and $U_2=2$. You have $|N(U_1)|=2,|N(U_2)|=1,|N(U_1 cup U_2)|=2$ and $|N(U_1 cap U_2)|=0$. So $2+1 ge 2+0$ holds as an inequality, not an equality.
Go over your proof-of-equality carefully, and see where the error is. In all likelihood your argument will let you show the inequality.
answered Jul 22 at 8:36
Alon Amit
10.2k3765
edited Jul 23 at 8:43
answered Jul 22 at 8:36
Alon Amit
10.2k3765
answered Jul 22 at 8:36
Alon Amit
10.2k3765
answered Jul 22 at 8:36
Alon Amit
10.2k3765
10.2k3765
add a comment |Â
add a comment |Â
up vote
0
down vote
Consider four set of vertices from $V$, defined as follows:
- $V_1 = N(U_1 cap U_2)$, vertices connected to the vertices common to $U_1$ and $U_2$
- $V_2 = (N(U_1)cap N(U_2))backslash V_1$, the vertices other than $V_1$ connected to both $U_1$ and $U_2$
- $V_3 = N(U_1)backslash (V_1cup V_2)$, vertices connected to $U_1$ but not $U_2$
- $V_4 = N(U_2)backslash (V_1cup V_2)$, vertices connected to $U_2$ but not $U_1$
Then
- $|N(U_1)|=|V_1|+|V_2|+|V_3|,$
- $|N(U_2)|=|V_1|+|V_2|+|V_4|,$
- $|N(U_1cup U_2)|=|V_1|+|V_2|+|V_3|+|V_4|,$ and
- $|N(U_1cap U_2)|=|V_1|$
and the inequality follows, of size $|V_2|$.
answered Jul 22 at 15:48
Joffan
31.8k43169
add a comment |Â
up vote
0
down vote
Consider four set of vertices from $V$, defined as follows:
- $V_1 = N(U_1 cap U_2)$, vertices connected to the vertices common to $U_1$ and $U_2$
- $V_2 = (N(U_1)cap N(U_2))backslash V_1$, the vertices other than $V_1$ connected to both $U_1$ and $U_2$
- $V_3 = N(U_1)backslash (V_1cup V_2)$, vertices connected to $U_1$ but not $U_2$
- $V_4 = N(U_2)backslash (V_1cup V_2)$, vertices connected to $U_2$ but not $U_1$
Then
- $|N(U_1)|=|V_1|+|V_2|+|V_3|,$
- $|N(U_2)|=|V_1|+|V_2|+|V_4|,$
- $|N(U_1cup U_2)|=|V_1|+|V_2|+|V_3|+|V_4|,$ and
- $|N(U_1cap U_2)|=|V_1|$
and the inequality follows, of size $|V_2|$.
answered Jul 22 at 15:48
Joffan
31.8k43169
add a comment |Â
up vote
0
down vote
up vote
0
down vote
Consider four set of vertices from $V$, defined as follows:
- $V_1 = N(U_1 cap U_2)$, vertices connected to the vertices common to $U_1$ and $U_2$
- $V_2 = (N(U_1)cap N(U_2))backslash V_1$, the vertices other than $V_1$ connected to both $U_1$ and $U_2$
- $V_3 = N(U_1)backslash (V_1cup V_2)$, vertices connected to $U_1$ but not $U_2$
- $V_4 = N(U_2)backslash (V_1cup V_2)$, vertices connected to $U_2$ but not $U_1$
Then
- $|N(U_1)|=|V_1|+|V_2|+|V_3|,$
- $|N(U_2)|=|V_1|+|V_2|+|V_4|,$
- $|N(U_1cup U_2)|=|V_1|+|V_2|+|V_3|+|V_4|,$ and
- $|N(U_1cap U_2)|=|V_1|$
and the inequality follows, of size $|V_2|$.
answered Jul 22 at 15:48
Joffan
31.8k43169
Consider four set of vertices from $V$, defined as follows:
- $V_1 = N(U_1 cap U_2)$, vertices connected to the vertices common to $U_1$ and $U_2$
- $V_2 = (N(U_1)cap N(U_2))backslash V_1$, the vertices other than $V_1$ connected to both $U_1$ and $U_2$
- $V_3 = N(U_1)backslash (V_1cup V_2)$, vertices connected to $U_1$ but not $U_2$
- $V_4 = N(U_2)backslash (V_1cup V_2)$, vertices connected to $U_2$ but not $U_1$
Then
- $|N(U_1)|=|V_1|+|V_2|+|V_3|,$
- $|N(U_2)|=|V_1|+|V_2|+|V_4|,$
- $|N(U_1cup U_2)|=|V_1|+|V_2|+|V_3|+|V_4|,$ and
- $|N(U_1cap U_2)|=|V_1|$
and the inequality follows, of size $|V_2|$.
answered Jul 22 at 15:48
Joffan
31.8k43169
answered Jul 22 at 15:48
Joffan
31.8k43169
answered Jul 22 at 15:48
Joffan
31.8k43169
answered Jul 22 at 15:48
Joffan
31.8k43169
31.8k43169
add a comment |Â
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%2f2859187%2fbipartite-graphs-neighborhood-size%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
for each vertex in $V$ think about which of the four sets can it belong to.
– Roronoa Zoro
Jul 22 at 7:39