Mixing
Prove that $|N_G(v)cap Y|=d_B(v)$
0
$begingroup$
G is a graph and B is a spanning bipartite subgraph of G such that B=B(X,Y) and v is any vertex in G
My work:
I know that $d_B(v)=|N_B(v)|$
So we have to prove that
$N_B(v)=N_G(v)cap Y$
It's clear that $N_B(v)supseteq N_G(v)cap Y$
is always true
I tried to prove the second direction by contradiction and I got $exists vyin E(G),yin Y/vynotin E(B)$
What should I do next ?
Thanks in advance
graph-theory
asked Jan 2 at 15:53
Any BanyAny Bany
31
$endgroup$
|
show 5 more comments
0
$begingroup$
G is a graph and B is a spanning bipartite subgraph of G such that B=B(X,Y) and v is any vertex in G
My work:
I know that $d_B(v)=|N_B(v)|$
So we have to prove that
$N_B(v)=N_G(v)cap Y$
It's clear that $N_B(v)supseteq N_G(v)cap Y$
is always true
I tried to prove the second direction by contradiction and I got $exists vyin E(G),yin Y/vynotin E(B)$
What should I do next ?
Thanks in advance
graph-theory
asked Jan 2 at 15:53
Any BanyAny Bany
31
$endgroup$
$begingroup$
If I understood the problem and your notations right, $v$ should be in $X$ (instead of $V(G)$) and the equality holds because $d_B(v)=|N_B(v)|$ and $$N_B(v)={uin V(B): (v,u)in E(G)}= $$ $${uin Y: (v,u)in E(G)}=N_G(v)cap Y.$$
$endgroup$
– Alex Ravsky
Jan 2 at 16:19
$begingroup$
I understand why equality holds, but I wanted to give a proof by contradiction. BTW v is in X (sorry)
$endgroup$
– Any Bany
Jan 2 at 16:43
$begingroup$
Oh. I think in order to have the equality, $B$ should be an induced subgraph of $G$, that is $E(B)={v’v’’in E(G): v’,v’’in B}$. Then we got a contradiction, because if $yin Y$ then $vyin E(B)$, right?
$endgroup$
– Alex Ravsky
Jan 2 at 16:53
$begingroup$
Okay I understand your point but what if B was spanning subgraph.
$endgroup$
– Any Bany
Jan 2 at 17:31
$begingroup$
If $B$ is not induced then the equality may fail. For instance, let $G$ be a complete graph with $|V(G)|=2n$ and let $V(G)=Xcup Y$ is a partition of $V(G)$ into two equal parts. Let $f:Xto Y$ be any bijection and $E(B)={xf(x):xin X}$. Then for each $vin X$, $d_B(v)=1$, but $|N_G(v)cap Y|=|Y|=n$.
$endgroup$
– Alex Ravsky
Jan 2 at 17:57
|
show 5 more comments
0
0
0
0
$begingroup$
G is a graph and B is a spanning bipartite subgraph of G such that B=B(X,Y) and v is any vertex in G
My work:
I know that $d_B(v)=|N_B(v)|$
So we have to prove that
$N_B(v)=N_G(v)cap Y$
It's clear that $N_B(v)supseteq N_G(v)cap Y$
is always true
I tried to prove the second direction by contradiction and I got $exists vyin E(G),yin Y/vynotin E(B)$
What should I do next ?
Thanks in advance
graph-theory
asked Jan 2 at 15:53
Any BanyAny Bany
31
$endgroup$
G is a graph and B is a spanning bipartite subgraph of G such that B=B(X,Y) and v is any vertex in G
My work:
I know that $d_B(v)=|N_B(v)|$
So we have to prove that
$N_B(v)=N_G(v)cap Y$
It's clear that $N_B(v)supseteq N_G(v)cap Y$
is always true
I tried to prove the second direction by contradiction and I got $exists vyin E(G),yin Y/vynotin E(B)$
What should I do next ?
Thanks in advance
graph-theory
graph-theory
asked Jan 2 at 15:53
Any BanyAny Bany
31
asked Jan 2 at 15:53
Any BanyAny Bany
31
asked Jan 2 at 15:53
Any BanyAny Bany
31
asked Jan 2 at 15:53
Any BanyAny Bany
31
asked Jan 2 at 15:53
Any BanyAny Bany
31
31
$begingroup$
If I understood the problem and your notations right, $v$ should be in $X$ (instead of $V(G)$) and the equality holds because $d_B(v)=|N_B(v)|$ and $$N_B(v)={uin V(B): (v,u)in E(G)}= $$ $${uin Y: (v,u)in E(G)}=N_G(v)cap Y.$$
$endgroup$
– Alex Ravsky
Jan 2 at 16:19
$begingroup$
I understand why equality holds, but I wanted to give a proof by contradiction. BTW v is in X (sorry)
$endgroup$
– Any Bany
Jan 2 at 16:43
$begingroup$
Oh. I think in order to have the equality, $B$ should be an induced subgraph of $G$, that is $E(B)={v’v’’in E(G): v’,v’’in B}$. Then we got a contradiction, because if $yin Y$ then $vyin E(B)$, right?
$endgroup$
– Alex Ravsky
Jan 2 at 16:53
$begingroup$
Okay I understand your point but what if B was spanning subgraph.
$endgroup$
– Any Bany
Jan 2 at 17:31
$begingroup$
If $B$ is not induced then the equality may fail. For instance, let $G$ be a complete graph with $|V(G)|=2n$ and let $V(G)=Xcup Y$ is a partition of $V(G)$ into two equal parts. Let $f:Xto Y$ be any bijection and $E(B)={xf(x):xin X}$. Then for each $vin X$, $d_B(v)=1$, but $|N_G(v)cap Y|=|Y|=n$.
$endgroup$
– Alex Ravsky
Jan 2 at 17:57
|
show 5 more comments
$begingroup$
If I understood the problem and your notations right, $v$ should be in $X$ (instead of $V(G)$) and the equality holds because $d_B(v)=|N_B(v)|$ and $$N_B(v)={uin V(B): (v,u)in E(G)}= $$ $${uin Y: (v,u)in E(G)}=N_G(v)cap Y.$$
$endgroup$
– Alex Ravsky
Jan 2 at 16:19
$begingroup$
I understand why equality holds, but I wanted to give a proof by contradiction. BTW v is in X (sorry)
$endgroup$
– Any Bany
Jan 2 at 16:43
$begingroup$
Oh. I think in order to have the equality, $B$ should be an induced subgraph of $G$, that is $E(B)={v’v’’in E(G): v’,v’’in B}$. Then we got a contradiction, because if $yin Y$ then $vyin E(B)$, right?
$endgroup$
– Alex Ravsky
Jan 2 at 16:53
$begingroup$
Okay I understand your point but what if B was spanning subgraph.
$endgroup$
– Any Bany
Jan 2 at 17:31
$begingroup$
If $B$ is not induced then the equality may fail. For instance, let $G$ be a complete graph with $|V(G)|=2n$ and let $V(G)=Xcup Y$ is a partition of $V(G)$ into two equal parts. Let $f:Xto Y$ be any bijection and $E(B)={xf(x):xin X}$. Then for each $vin X$, $d_B(v)=1$, but $|N_G(v)cap Y|=|Y|=n$.
$endgroup$
– Alex Ravsky
Jan 2 at 17:57
$begingroup$
If I understood the problem and your notations right, $v$ should be in $X$ (instead of $V(G)$) and the equality holds because $d_B(v)=|N_B(v)|$ and $$N_B(v)={uin V(B): (v,u)in E(G)}= $$ $${uin Y: (v,u)in E(G)}=N_G(v)cap Y.$$
$endgroup$
– Alex Ravsky
Jan 2 at 16:19
$begingroup$
If I understood the problem and your notations right, $v$ should be in $X$ (instead of $V(G)$) and the equality holds because $d_B(v)=|N_B(v)|$ and $$N_B(v)={uin V(B): (v,u)in E(G)}= $$ $${uin Y: (v,u)in E(G)}=N_G(v)cap Y.$$
$endgroup$
– Alex Ravsky
Jan 2 at 16:19
$begingroup$
I understand why equality holds, but I wanted to give a proof by contradiction. BTW v is in X (sorry)
$endgroup$
– Any Bany
Jan 2 at 16:43
$begingroup$
I understand why equality holds, but I wanted to give a proof by contradiction. BTW v is in X (sorry)
$endgroup$
– Any Bany
Jan 2 at 16:43
$begingroup$
Oh. I think in order to have the equality, $B$ should be an induced subgraph of $G$, that is $E(B)={v’v’’in E(G): v’,v’’in B}$. Then we got a contradiction, because if $yin Y$ then $vyin E(B)$, right?
$endgroup$
– Alex Ravsky
Jan 2 at 16:53
$begingroup$
Oh. I think in order to have the equality, $B$ should be an induced subgraph of $G$, that is $E(B)={v’v’’in E(G): v’,v’’in B}$. Then we got a contradiction, because if $yin Y$ then $vyin E(B)$, right?
$endgroup$
– Alex Ravsky
Jan 2 at 16:53
$begingroup$
Okay I understand your point but what if B was spanning subgraph.
$endgroup$
– Any Bany
Jan 2 at 17:31
$begingroup$
Okay I understand your point but what if B was spanning subgraph.
$endgroup$
– Any Bany
Jan 2 at 17:31
$begingroup$
If $B$ is not induced then the equality may fail. For instance, let $G$ be a complete graph with $|V(G)|=2n$ and let $V(G)=Xcup Y$ is a partition of $V(G)$ into two equal parts. Let $f:Xto Y$ be any bijection and $E(B)={xf(x):xin X}$. Then for each $vin X$, $d_B(v)=1$, but $|N_G(v)cap Y|=|Y|=n$.
$endgroup$
– Alex Ravsky
Jan 2 at 17:57
$begingroup$
If $B$ is not induced then the equality may fail. For instance, let $G$ be a complete graph with $|V(G)|=2n$ and let $V(G)=Xcup Y$ is a partition of $V(G)$ into two equal parts. Let $f:Xto Y$ be any bijection and $E(B)={xf(x):xin X}$. Then for each $vin X$, $d_B(v)=1$, but $|N_G(v)cap Y|=|Y|=n$.
$endgroup$
– Alex Ravsky
Jan 2 at 17:57
|
show 5 more comments
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
draft saved
draft discarded
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3059637%2fprove-that-n-gv-cap-y-d-bv%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
draft saved
draft discarded
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
draft saved
draft discarded
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3059637%2fprove-that-n-gv-cap-y-d-bv%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
If I understood the problem and your notations right, $v$ should be in $X$ (instead of $V(G)$) and the equality holds because $d_B(v)=|N_B(v)|$ and $$N_B(v)={uin V(B): (v,u)in E(G)}= $$ $${uin Y: (v,u)in E(G)}=N_G(v)cap Y.$$
$endgroup$
– Alex Ravsky
Jan 2 at 16:19
$begingroup$
I understand why equality holds, but I wanted to give a proof by contradiction. BTW v is in X (sorry)
$endgroup$
– Any Bany
Jan 2 at 16:43
$begingroup$
Oh. I think in order to have the equality, $B$ should be an induced subgraph of $G$, that is $E(B)={v’v’’in E(G): v’,v’’in B}$. Then we got a contradiction, because if $yin Y$ then $vyin E(B)$, right?
$endgroup$
– Alex Ravsky
Jan 2 at 16:53
$begingroup$
Okay I understand your point but what if B was spanning subgraph.
$endgroup$
– Any Bany
Jan 2 at 17:31
$begingroup$
If $B$ is not induced then the equality may fail. For instance, let $G$ be a complete graph with $|V(G)|=2n$ and let $V(G)=Xcup Y$ is a partition of $V(G)$ into two equal parts. Let $f:Xto Y$ be any bijection and $E(B)={xf(x):xin X}$. Then for each $vin X$, $d_B(v)=1$, but $|N_G(v)cap Y|=|Y|=n$.
$endgroup$
– Alex Ravsky
Jan 2 at 17:57