Mixing
Proving if a graph is connected
$begingroup$
How can I prove this theorem:
For a graph with n vertices, if the degree of each vertex is at least n/2, then
G is connected.
graph-theory
asked Jan 31 at 14:04
choptxenchoptxen
112
$endgroup$
add a comment |
$begingroup$
How can I prove this theorem:
For a graph with n vertices, if the degree of each vertex is at least n/2, then
G is connected.
graph-theory
asked Jan 31 at 14:04
choptxenchoptxen
112
$endgroup$
$begingroup$
Hint: Consider two distinct vertices $u,v$. Is it possible that they have no neighbor in common?
$endgroup$
– hardmath
Jan 31 at 14:09
1
$begingroup$
Remark that it only works if you do not permit multiple edges between points in your graph definition.
$endgroup$
– Paul Cottalorda
Jan 31 at 14:11
add a comment |
$begingroup$
How can I prove this theorem:
For a graph with n vertices, if the degree of each vertex is at least n/2, then
G is connected.
graph-theory
asked Jan 31 at 14:04
choptxenchoptxen
112
$endgroup$
How can I prove this theorem:
For a graph with n vertices, if the degree of each vertex is at least n/2, then
G is connected.
graph-theory
graph-theory
asked Jan 31 at 14:04
choptxenchoptxen
112
asked Jan 31 at 14:04
choptxenchoptxen
112
asked Jan 31 at 14:04
choptxenchoptxen
112
asked Jan 31 at 14:04
choptxenchoptxen
112
asked Jan 31 at 14:04
choptxenchoptxen
112
112
$begingroup$
Hint: Consider two distinct vertices $u,v$. Is it possible that they have no neighbor in common?
$endgroup$
– hardmath
Jan 31 at 14:09
1
$begingroup$
Remark that it only works if you do not permit multiple edges between points in your graph definition.
$endgroup$
– Paul Cottalorda
Jan 31 at 14:11
add a comment |
$begingroup$
Hint: Consider two distinct vertices $u,v$. Is it possible that they have no neighbor in common?
$endgroup$
– hardmath
Jan 31 at 14:09
1
$begingroup$
Remark that it only works if you do not permit multiple edges between points in your graph definition.
$endgroup$
– Paul Cottalorda
Jan 31 at 14:11
$begingroup$
Hint: Consider two distinct vertices $u,v$. Is it possible that they have no neighbor in common?
$endgroup$
– hardmath
Jan 31 at 14:09
$begingroup$
Hint: Consider two distinct vertices $u,v$. Is it possible that they have no neighbor in common?
$endgroup$
– hardmath
Jan 31 at 14:09
1
1
$begingroup$
Remark that it only works if you do not permit multiple edges between points in your graph definition.
$endgroup$
– Paul Cottalorda
Jan 31 at 14:11
$begingroup$
Remark that it only works if you do not permit multiple edges between points in your graph definition.
$endgroup$
– Paul Cottalorda
Jan 31 at 14:11
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
If every vertex has degree at least $frac{n}{2}$, then every connected component has at least $frac{n}{2}+1$ vertices. Clearly, there can only be one component now.
answered Jan 31 at 14:07
KlausKlaus
2,955214
$endgroup$
add a comment |
$begingroup$
I'm not a topologist, but this clearly depends on the definition of the degree of a vertex.
If degree refers solely to the number of edges meeting at a vertex and there can be multiple edges between two vertices, then the theorem doesn't hold for $n>3$. We can simply divide the vertices into pairs (plus one group of $3$ if $n$ is odd), then draw $geq frac{n}{2}$ edges between each pair while keeping the pairs disconnected from each other. (This requires at least $2$ pairs, so at least $4$ vertices.)
If degree refers to the number of distinct vertices a vertex is directly connected to, or multiple edges between two vertices are not allowed, then see Klaus' answer.
answered Jan 31 at 15:47
timtfjtimtfj
2,503420
$endgroup$
add a comment |
$begingroup$
To prove that the graph is connected it is sufficient to show that taken any 2 vertices in graph G say u and v, there exists a path between them. But it can be clearly seen that the degree sum of 2 vertices is greater n which implies that there is at least one common neighbor for both u and v. Hence there always exists a path between any 2 vertices of the graph. Hence the graph is connected.
answered Feb 1 at 13:41
Ayush ChaurasiaAyush Chaurasia
12
$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%2f3094918%2fproving-if-a-graph-is-connected%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
If every vertex has degree at least $frac{n}{2}$, then every connected component has at least $frac{n}{2}+1$ vertices. Clearly, there can only be one component now.
answered Jan 31 at 14:07
KlausKlaus
2,955214
$endgroup$
add a comment |
$begingroup$
If every vertex has degree at least $frac{n}{2}$, then every connected component has at least $frac{n}{2}+1$ vertices. Clearly, there can only be one component now.
answered Jan 31 at 14:07
KlausKlaus
2,955214
$endgroup$
add a comment |
$begingroup$
If every vertex has degree at least $frac{n}{2}$, then every connected component has at least $frac{n}{2}+1$ vertices. Clearly, there can only be one component now.
answered Jan 31 at 14:07
KlausKlaus
2,955214
$endgroup$
If every vertex has degree at least $frac{n}{2}$, then every connected component has at least $frac{n}{2}+1$ vertices. Clearly, there can only be one component now.
answered Jan 31 at 14:07
KlausKlaus
2,955214
answered Jan 31 at 14:07
KlausKlaus
2,955214
answered Jan 31 at 14:07
KlausKlaus
2,955214
answered Jan 31 at 14:07
KlausKlaus
2,955214
2,955214
add a comment |
add a comment |
$begingroup$
I'm not a topologist, but this clearly depends on the definition of the degree of a vertex.
If degree refers solely to the number of edges meeting at a vertex and there can be multiple edges between two vertices, then the theorem doesn't hold for $n>3$. We can simply divide the vertices into pairs (plus one group of $3$ if $n$ is odd), then draw $geq frac{n}{2}$ edges between each pair while keeping the pairs disconnected from each other. (This requires at least $2$ pairs, so at least $4$ vertices.)
If degree refers to the number of distinct vertices a vertex is directly connected to, or multiple edges between two vertices are not allowed, then see Klaus' answer.
answered Jan 31 at 15:47
timtfjtimtfj
2,503420
$endgroup$
add a comment |
$begingroup$
I'm not a topologist, but this clearly depends on the definition of the degree of a vertex.
If degree refers solely to the number of edges meeting at a vertex and there can be multiple edges between two vertices, then the theorem doesn't hold for $n>3$. We can simply divide the vertices into pairs (plus one group of $3$ if $n$ is odd), then draw $geq frac{n}{2}$ edges between each pair while keeping the pairs disconnected from each other. (This requires at least $2$ pairs, so at least $4$ vertices.)
If degree refers to the number of distinct vertices a vertex is directly connected to, or multiple edges between two vertices are not allowed, then see Klaus' answer.
answered Jan 31 at 15:47
timtfjtimtfj
2,503420
$endgroup$
add a comment |
$begingroup$
I'm not a topologist, but this clearly depends on the definition of the degree of a vertex.
If degree refers solely to the number of edges meeting at a vertex and there can be multiple edges between two vertices, then the theorem doesn't hold for $n>3$. We can simply divide the vertices into pairs (plus one group of $3$ if $n$ is odd), then draw $geq frac{n}{2}$ edges between each pair while keeping the pairs disconnected from each other. (This requires at least $2$ pairs, so at least $4$ vertices.)
If degree refers to the number of distinct vertices a vertex is directly connected to, or multiple edges between two vertices are not allowed, then see Klaus' answer.
answered Jan 31 at 15:47
timtfjtimtfj
2,503420
$endgroup$
I'm not a topologist, but this clearly depends on the definition of the degree of a vertex.
If degree refers solely to the number of edges meeting at a vertex and there can be multiple edges between two vertices, then the theorem doesn't hold for $n>3$. We can simply divide the vertices into pairs (plus one group of $3$ if $n$ is odd), then draw $geq frac{n}{2}$ edges between each pair while keeping the pairs disconnected from each other. (This requires at least $2$ pairs, so at least $4$ vertices.)
If degree refers to the number of distinct vertices a vertex is directly connected to, or multiple edges between two vertices are not allowed, then see Klaus' answer.
answered Jan 31 at 15:47
timtfjtimtfj
2,503420
edited Jan 31 at 15:55
answered Jan 31 at 15:47
timtfjtimtfj
2,503420
answered Jan 31 at 15:47
timtfjtimtfj
2,503420
answered Jan 31 at 15:47
timtfjtimtfj
2,503420
2,503420
add a comment |
add a comment |
$begingroup$
To prove that the graph is connected it is sufficient to show that taken any 2 vertices in graph G say u and v, there exists a path between them. But it can be clearly seen that the degree sum of 2 vertices is greater n which implies that there is at least one common neighbor for both u and v. Hence there always exists a path between any 2 vertices of the graph. Hence the graph is connected.
answered Feb 1 at 13:41
Ayush ChaurasiaAyush Chaurasia
12
$endgroup$
add a comment |
$begingroup$
To prove that the graph is connected it is sufficient to show that taken any 2 vertices in graph G say u and v, there exists a path between them. But it can be clearly seen that the degree sum of 2 vertices is greater n which implies that there is at least one common neighbor for both u and v. Hence there always exists a path between any 2 vertices of the graph. Hence the graph is connected.
answered Feb 1 at 13:41
Ayush ChaurasiaAyush Chaurasia
12
$endgroup$
add a comment |
$begingroup$
To prove that the graph is connected it is sufficient to show that taken any 2 vertices in graph G say u and v, there exists a path between them. But it can be clearly seen that the degree sum of 2 vertices is greater n which implies that there is at least one common neighbor for both u and v. Hence there always exists a path between any 2 vertices of the graph. Hence the graph is connected.
answered Feb 1 at 13:41
Ayush ChaurasiaAyush Chaurasia
12
$endgroup$
To prove that the graph is connected it is sufficient to show that taken any 2 vertices in graph G say u and v, there exists a path between them. But it can be clearly seen that the degree sum of 2 vertices is greater n which implies that there is at least one common neighbor for both u and v. Hence there always exists a path between any 2 vertices of the graph. Hence the graph is connected.
answered Feb 1 at 13:41
Ayush ChaurasiaAyush Chaurasia
12
answered Feb 1 at 13:41
Ayush ChaurasiaAyush Chaurasia
12
answered Feb 1 at 13:41
Ayush ChaurasiaAyush Chaurasia
12
answered Feb 1 at 13:41
Ayush ChaurasiaAyush Chaurasia
12
12
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%2f3094918%2fproving-if-a-graph-is-connected%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$
Hint: Consider two distinct vertices $u,v$. Is it possible that they have no neighbor in common?
$endgroup$
– hardmath
Jan 31 at 14:09
1
$begingroup$
Remark that it only works if you do not permit multiple edges between points in your graph definition.
$endgroup$
– Paul Cottalorda
Jan 31 at 14:11