Mixing
Proving that there exists a path between two vertex in graph $G=(V,E)$
$begingroup$
Let $G=(V,E)$ be a finite undirected graph so vertex $xin V$ has odd rank.
I'm trying to prove that there must be vertex $yin V$ which has odd rank and there is a path between $x,y$. I feel like it a basic theorem but I didn't find any proof for it and I can't seem to think of one.
How to approach this problem?
graph-theory
asked Jan 13 at 20:57
vesiivesii
1156
$endgroup$
add a comment |
$begingroup$
Let $G=(V,E)$ be a finite undirected graph so vertex $xin V$ has odd rank.
I'm trying to prove that there must be vertex $yin V$ which has odd rank and there is a path between $x,y$. I feel like it a basic theorem but I didn't find any proof for it and I can't seem to think of one.
How to approach this problem?
graph-theory
asked Jan 13 at 20:57
vesiivesii
1156
$endgroup$
add a comment |
$begingroup$
Let $G=(V,E)$ be a finite undirected graph so vertex $xin V$ has odd rank.
I'm trying to prove that there must be vertex $yin V$ which has odd rank and there is a path between $x,y$. I feel like it a basic theorem but I didn't find any proof for it and I can't seem to think of one.
How to approach this problem?
graph-theory
asked Jan 13 at 20:57
vesiivesii
1156
$endgroup$
Let $G=(V,E)$ be a finite undirected graph so vertex $xin V$ has odd rank.
I'm trying to prove that there must be vertex $yin V$ which has odd rank and there is a path between $x,y$. I feel like it a basic theorem but I didn't find any proof for it and I can't seem to think of one.
How to approach this problem?
graph-theory
graph-theory
asked Jan 13 at 20:57
vesiivesii
1156
asked Jan 13 at 20:57
vesiivesii
1156
asked Jan 13 at 20:57
vesiivesii
1156
asked Jan 13 at 20:57
vesiivesii
1156
asked Jan 13 at 20:57
vesiivesii
1156
1156
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Given a connected component of a graph, the sum of the ranks of its vertices is precisely two times the number of edges, that is, an even number.
answered Jan 13 at 21:02
ajotatxeajotatxe
53.8k23890
$endgroup$
$begingroup$
Yes I know that theorem, but how does it prove?
$endgroup$
– vesii
Jan 13 at 21:05
add a comment |
$begingroup$
As explained by ajotatxe :
Given a connected component of a graph, the sum of the ranks of its vertices is precisely two times the number of edges, that is, an even number.
Let $H$ be the connected component including $x$, of odd degree : $d(x)=2k+1$. Let $m$ be the number of edges in $H$ :
$$ sum_{i in V(H)} d(i) = 2m$$
$$ sum_{i in V(H)backslash{x}} d(i) = 2m - d(x) = 2k'+1$$
Therefore there must exist $y in V(H)backslash{x}$ such that $d(y)$ is odd, and $y in V(H)$ implies that there exist a path from $x$ to $y$.
answered Jan 14 at 19:07
Thomas LesgourguesThomas Lesgourgues
795117
$endgroup$
add a comment |
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
});
}
});
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%2f3072508%2fproving-that-there-exists-a-path-between-two-vertex-in-graph-g-v-e%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Given a connected component of a graph, the sum of the ranks of its vertices is precisely two times the number of edges, that is, an even number.
answered Jan 13 at 21:02
ajotatxeajotatxe
53.8k23890
$endgroup$
$begingroup$
Yes I know that theorem, but how does it prove?
$endgroup$
– vesii
Jan 13 at 21:05
add a comment |
$begingroup$
Given a connected component of a graph, the sum of the ranks of its vertices is precisely two times the number of edges, that is, an even number.
answered Jan 13 at 21:02
ajotatxeajotatxe
53.8k23890
$endgroup$
$begingroup$
Yes I know that theorem, but how does it prove?
$endgroup$
– vesii
Jan 13 at 21:05
add a comment |
$begingroup$
Given a connected component of a graph, the sum of the ranks of its vertices is precisely two times the number of edges, that is, an even number.
answered Jan 13 at 21:02
ajotatxeajotatxe
53.8k23890
$endgroup$
Given a connected component of a graph, the sum of the ranks of its vertices is precisely two times the number of edges, that is, an even number.
answered Jan 13 at 21:02
ajotatxeajotatxe
53.8k23890
answered Jan 13 at 21:02
ajotatxeajotatxe
53.8k23890
answered Jan 13 at 21:02
ajotatxeajotatxe
53.8k23890
answered Jan 13 at 21:02
ajotatxeajotatxe
53.8k23890
53.8k23890
$begingroup$
Yes I know that theorem, but how does it prove?
$endgroup$
– vesii
Jan 13 at 21:05
add a comment |
$begingroup$
Yes I know that theorem, but how does it prove?
$endgroup$
– vesii
Jan 13 at 21:05
$begingroup$
Yes I know that theorem, but how does it prove?
$endgroup$
– vesii
Jan 13 at 21:05
$begingroup$
Yes I know that theorem, but how does it prove?
$endgroup$
– vesii
Jan 13 at 21:05
add a comment |
$begingroup$
As explained by ajotatxe :
Given a connected component of a graph, the sum of the ranks of its vertices is precisely two times the number of edges, that is, an even number.
Let $H$ be the connected component including $x$, of odd degree : $d(x)=2k+1$. Let $m$ be the number of edges in $H$ :
$$ sum_{i in V(H)} d(i) = 2m$$
$$ sum_{i in V(H)backslash{x}} d(i) = 2m - d(x) = 2k'+1$$
Therefore there must exist $y in V(H)backslash{x}$ such that $d(y)$ is odd, and $y in V(H)$ implies that there exist a path from $x$ to $y$.
answered Jan 14 at 19:07
Thomas LesgourguesThomas Lesgourgues
795117
$endgroup$
add a comment |
$begingroup$
As explained by ajotatxe :
Given a connected component of a graph, the sum of the ranks of its vertices is precisely two times the number of edges, that is, an even number.
Let $H$ be the connected component including $x$, of odd degree : $d(x)=2k+1$. Let $m$ be the number of edges in $H$ :
$$ sum_{i in V(H)} d(i) = 2m$$
$$ sum_{i in V(H)backslash{x}} d(i) = 2m - d(x) = 2k'+1$$
Therefore there must exist $y in V(H)backslash{x}$ such that $d(y)$ is odd, and $y in V(H)$ implies that there exist a path from $x$ to $y$.
answered Jan 14 at 19:07
Thomas LesgourguesThomas Lesgourgues
795117
$endgroup$
add a comment |
$begingroup$
As explained by ajotatxe :
Given a connected component of a graph, the sum of the ranks of its vertices is precisely two times the number of edges, that is, an even number.
Let $H$ be the connected component including $x$, of odd degree : $d(x)=2k+1$. Let $m$ be the number of edges in $H$ :
$$ sum_{i in V(H)} d(i) = 2m$$
$$ sum_{i in V(H)backslash{x}} d(i) = 2m - d(x) = 2k'+1$$
Therefore there must exist $y in V(H)backslash{x}$ such that $d(y)$ is odd, and $y in V(H)$ implies that there exist a path from $x$ to $y$.
answered Jan 14 at 19:07
Thomas LesgourguesThomas Lesgourgues
795117
$endgroup$
As explained by ajotatxe :
Given a connected component of a graph, the sum of the ranks of its vertices is precisely two times the number of edges, that is, an even number.
Let $H$ be the connected component including $x$, of odd degree : $d(x)=2k+1$. Let $m$ be the number of edges in $H$ :
$$ sum_{i in V(H)} d(i) = 2m$$
$$ sum_{i in V(H)backslash{x}} d(i) = 2m - d(x) = 2k'+1$$
Therefore there must exist $y in V(H)backslash{x}$ such that $d(y)$ is odd, and $y in V(H)$ implies that there exist a path from $x$ to $y$.
answered Jan 14 at 19:07
Thomas LesgourguesThomas Lesgourgues
795117
answered Jan 14 at 19:07
Thomas LesgourguesThomas Lesgourgues
795117
answered Jan 14 at 19:07
Thomas LesgourguesThomas Lesgourgues
795117
answered Jan 14 at 19:07
Thomas LesgourguesThomas Lesgourgues
795117
795117
add a comment |
add a comment |
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.
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%2f3072508%2fproving-that-there-exists-a-path-between-two-vertex-in-graph-g-v-e%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
