How to prove that at least two vertices have the same degree in any graph?
$begingroup$
I want to prove that at least two vertices have the same degree in any graph (with 2 or more vertices). I do have a few graphs in mind that prove this statement correct, but how would I go about proving it (or disproving it) for ALL graphs?
combinatorics discrete-mathematics graph-theory
edited 3 hours ago
James Rettie
31
asked 9 hours ago
desiignerdesiigner
625
$endgroup$
add a comment |
$begingroup$
I want to prove that at least two vertices have the same degree in any graph (with 2 or more vertices). I do have a few graphs in mind that prove this statement correct, but how would I go about proving it (or disproving it) for ALL graphs?
combinatorics discrete-mathematics graph-theory
edited 3 hours ago
James Rettie
31
asked 9 hours ago
desiignerdesiigner
625
$endgroup$
1
$begingroup$
Please try to make the titles of your questions more informative. For example, Why does $a<b$ imply $a+c<b+c$? is much more useful for other users than A question about inequality. From How can I ask a good question?: Make your title as descriptive as possible. In many cases one can actually phrase the title as the question, at least in such a way so as to be comprehensible to an expert reader. You can find more tips for choosing a good title here.
$endgroup$
– Shaun
9 hours ago
1
$begingroup$
Symmetric, simple graphs?
$endgroup$
– Mindlack
9 hours ago
2
$begingroup$
Possible duplicate of "In a party people shake hands with one another"
$endgroup$
– JMoravitz
9 hours ago
$begingroup$
Possible duplicate of If n is a natural number ≥2 how do I prove that any graph with n vertices has at least two vertices of the same degree?
$endgroup$
– Acccumulation
4 hours ago
add a comment |
$begingroup$
I want to prove that at least two vertices have the same degree in any graph (with 2 or more vertices). I do have a few graphs in mind that prove this statement correct, but how would I go about proving it (or disproving it) for ALL graphs?
combinatorics discrete-mathematics graph-theory
edited 3 hours ago
James Rettie
31
asked 9 hours ago
desiignerdesiigner
625
$endgroup$
I want to prove that at least two vertices have the same degree in any graph (with 2 or more vertices). I do have a few graphs in mind that prove this statement correct, but how would I go about proving it (or disproving it) for ALL graphs?
combinatorics discrete-mathematics graph-theory
combinatorics discrete-mathematics graph-theory
edited 3 hours ago
James Rettie
31
asked 9 hours ago
desiignerdesiigner
625
edited 3 hours ago
James Rettie
31
asked 9 hours ago
desiignerdesiigner
625
edited 3 hours ago
James Rettie
31
edited 3 hours ago
James Rettie
31
edited 3 hours ago
James Rettie
31
31
asked 9 hours ago
desiignerdesiigner
625
asked 9 hours ago
desiignerdesiigner
625
asked 9 hours ago
desiignerdesiigner
625
625
1
$begingroup$
Please try to make the titles of your questions more informative. For example, Why does $a<b$ imply $a+c<b+c$? is much more useful for other users than A question about inequality. From How can I ask a good question?: Make your title as descriptive as possible. In many cases one can actually phrase the title as the question, at least in such a way so as to be comprehensible to an expert reader. You can find more tips for choosing a good title here.
$endgroup$
– Shaun
9 hours ago
1
$begingroup$
Symmetric, simple graphs?
$endgroup$
– Mindlack
9 hours ago
2
$begingroup$
Possible duplicate of "In a party people shake hands with one another"
$endgroup$
– JMoravitz
9 hours ago
$begingroup$
Possible duplicate of If n is a natural number ≥2 how do I prove that any graph with n vertices has at least two vertices of the same degree?
$endgroup$
– Acccumulation
4 hours ago
add a comment |
1
$begingroup$
Please try to make the titles of your questions more informative. For example, Why does $a<b$ imply $a+c<b+c$? is much more useful for other users than A question about inequality. From How can I ask a good question?: Make your title as descriptive as possible. In many cases one can actually phrase the title as the question, at least in such a way so as to be comprehensible to an expert reader. You can find more tips for choosing a good title here.
$endgroup$
– Shaun
9 hours ago
1
$begingroup$
Symmetric, simple graphs?
$endgroup$
– Mindlack
9 hours ago
2
$begingroup$
Possible duplicate of "In a party people shake hands with one another"
$endgroup$
– JMoravitz
9 hours ago
$begingroup$
Possible duplicate of If n is a natural number ≥2 how do I prove that any graph with n vertices has at least two vertices of the same degree?
$endgroup$
– Acccumulation
4 hours ago
1
1
$begingroup$
Please try to make the titles of your questions more informative. For example, Why does $a<b$ imply $a+c<b+c$? is much more useful for other users than A question about inequality. From How can I ask a good question?: Make your title as descriptive as possible. In many cases one can actually phrase the title as the question, at least in such a way so as to be comprehensible to an expert reader. You can find more tips for choosing a good title here.
$endgroup$
– Shaun
9 hours ago
$begingroup$
Please try to make the titles of your questions more informative. For example, Why does $a<b$ imply $a+c<b+c$? is much more useful for other users than A question about inequality. From How can I ask a good question?: Make your title as descriptive as possible. In many cases one can actually phrase the title as the question, at least in such a way so as to be comprehensible to an expert reader. You can find more tips for choosing a good title here.
$endgroup$
– Shaun
9 hours ago
1
1
$begingroup$
Symmetric, simple graphs?
$endgroup$
– Mindlack
9 hours ago
$begingroup$
Symmetric, simple graphs?
$endgroup$
– Mindlack
9 hours ago
2
2
$begingroup$
Possible duplicate of "In a party people shake hands with one another"
$endgroup$
– JMoravitz
9 hours ago
$begingroup$
Possible duplicate of "In a party people shake hands with one another"
$endgroup$
– JMoravitz
9 hours ago
$begingroup$
Possible duplicate of If n is a natural number ≥2 how do I prove that any graph with n vertices has at least two vertices of the same degree?
$endgroup$
– Acccumulation
4 hours ago
$begingroup$
Possible duplicate of If n is a natural number ≥2 how do I prove that any graph with n vertices has at least two vertices of the same degree?
$endgroup$
– Acccumulation
4 hours ago
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
I assume we're talking about finite graphs. I'm pretty sure your statement is false for infinite graphs.
Assume that a finite graph $G$ has $n$ vertices. Then each vertex has a degree between $n-1$ and $0$. But if any vertex has degree $0$, then no vertex can have degree $n-1$, so it's not possible for the degrees of the graph's vertices to include both $0$ and $n-1$. Thus, the $n$ vertices of the graph can only have $n-1$ different degrees, so by the pigeonhole principle at least two vertices must have the same degree.
answered 9 hours ago
Robert ShoreRobert Shore
3116
New contributor
Robert Shore is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
$begingroup$
You are assuming the graph is simple?
$endgroup$
– Servaes
5 hours ago
1
$begingroup$
Yes. That is assumed in the definition of graph that I learned. I learned to call a graph with loops or multiple edges between vertices a "multigraph."
$endgroup$
– Robert Shore
4 hours ago
add a comment |
$begingroup$
Say graph is simple with no loops and that all vertices have different degree $d_1,d_2,...d_n$, then $${d_1,d_2,...d_n} = {0,1,2...,n-1}$$
So there is a vertex with degree $n-1$ and a vertex with degree $0$. A contradiction.
answered 9 hours ago
greedoidgreedoid
41k1149101
$endgroup$
$begingroup$
Perhaps it would be better to include that the graph is simple?
$endgroup$
– Shubham Johri
9 hours ago
$begingroup$
Is it necessary to specify "no loops"?
$endgroup$
– Shufflepants
4 hours ago
$begingroup$
Of course. Take a graph with two vertices and one connected to it self. @Shufflepants
$endgroup$
– greedoid
4 hours ago
1
$begingroup$
@greedoid Then by "no loops" did you mean "no self connection"? Otherwise I'd interpret "simple with no loops" as being equivalent to a tree. But in any case, the OP didn't specify "simple" or "no loops". So, it would seem the answer to the question is: it's not provable because it's not true.
$endgroup$
– Shufflepants
4 hours ago
1
$begingroup$
Because I didn't see it at first: This follows because in a simple graph the degree of any vertex must be less than the number of vertices. Thus if the vertex degrees are all different and less than $n$ they must be ${0, 1, 2..., n-1}$.
$endgroup$
– immibis
3 hours ago
|
show 1 more comment
$begingroup$
Here is a counterexample.
Let $G$ be a graph on the positive integers where there is an edge from $x$ to $y$ if $x < y le 2x$. Note that we will ignore the direction of the edges. So $2$, for example, is neighbored by $1$, $3$, and $4$.
Let $j$ and $k$ be distinct positive integers. Without loss of generality assume that $j < k$. Note that $deg(j) = j + lfloor j/2 rfloor$ and $deg(k) = k + lfloor k/2 rfloor$. We have that
$$j < k$$
$$lfloor j/2 rfloor le lfloor k/2 rfloor$$
$$j + lfloor j/2 rfloor < k + lfloor k/2 rfloor$$
$$deg(j) < deg(k)$$
$$deg(j) neq deg(k)$$
Therefore, no two different vertices will have the same degree. $square$
answered 4 hours ago
PyRulezPyRulez
4,68622469
$endgroup$
$begingroup$
As noted at en.wikipedia.org/wiki/Graph_theory#Definitions, "V and E are usually taken to be finite, and many of the well-known results are not true (or are rather different) for infinite graphs because many of the arguments fail in the infinite case."
$endgroup$
– ruakh
3 mins ago
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%2f3100174%2fhow-to-prove-that-at-least-two-vertices-have-the-same-degree-in-any-graph%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$
I assume we're talking about finite graphs. I'm pretty sure your statement is false for infinite graphs.
Assume that a finite graph $G$ has $n$ vertices. Then each vertex has a degree between $n-1$ and $0$. But if any vertex has degree $0$, then no vertex can have degree $n-1$, so it's not possible for the degrees of the graph's vertices to include both $0$ and $n-1$. Thus, the $n$ vertices of the graph can only have $n-1$ different degrees, so by the pigeonhole principle at least two vertices must have the same degree.
answered 9 hours ago
Robert ShoreRobert Shore
3116
New contributor
Robert Shore is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
$begingroup$
You are assuming the graph is simple?
$endgroup$
– Servaes
5 hours ago
1
$begingroup$
Yes. That is assumed in the definition of graph that I learned. I learned to call a graph with loops or multiple edges between vertices a "multigraph."
$endgroup$
– Robert Shore
4 hours ago
add a comment |
$begingroup$
I assume we're talking about finite graphs. I'm pretty sure your statement is false for infinite graphs.
Assume that a finite graph $G$ has $n$ vertices. Then each vertex has a degree between $n-1$ and $0$. But if any vertex has degree $0$, then no vertex can have degree $n-1$, so it's not possible for the degrees of the graph's vertices to include both $0$ and $n-1$. Thus, the $n$ vertices of the graph can only have $n-1$ different degrees, so by the pigeonhole principle at least two vertices must have the same degree.
answered 9 hours ago
Robert ShoreRobert Shore
3116
New contributor
Robert Shore is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
$begingroup$
You are assuming the graph is simple?
$endgroup$
– Servaes
5 hours ago
1
$begingroup$
Yes. That is assumed in the definition of graph that I learned. I learned to call a graph with loops or multiple edges between vertices a "multigraph."
$endgroup$
– Robert Shore
4 hours ago
add a comment |
$begingroup$
I assume we're talking about finite graphs. I'm pretty sure your statement is false for infinite graphs.
Assume that a finite graph $G$ has $n$ vertices. Then each vertex has a degree between $n-1$ and $0$. But if any vertex has degree $0$, then no vertex can have degree $n-1$, so it's not possible for the degrees of the graph's vertices to include both $0$ and $n-1$. Thus, the $n$ vertices of the graph can only have $n-1$ different degrees, so by the pigeonhole principle at least two vertices must have the same degree.
answered 9 hours ago
Robert ShoreRobert Shore
3116
New contributor
Robert Shore is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
I assume we're talking about finite graphs. I'm pretty sure your statement is false for infinite graphs.
Assume that a finite graph $G$ has $n$ vertices. Then each vertex has a degree between $n-1$ and $0$. But if any vertex has degree $0$, then no vertex can have degree $n-1$, so it's not possible for the degrees of the graph's vertices to include both $0$ and $n-1$. Thus, the $n$ vertices of the graph can only have $n-1$ different degrees, so by the pigeonhole principle at least two vertices must have the same degree.
answered 9 hours ago
Robert ShoreRobert Shore
3116
New contributor
Robert Shore is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered 9 hours ago
Robert ShoreRobert Shore
3116
New contributor
Robert Shore is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered 9 hours ago
Robert ShoreRobert Shore
3116
answered 9 hours ago
Robert ShoreRobert Shore
3116
3116
New contributor
Robert Shore is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Robert Shore is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Robert Shore is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$begingroup$
You are assuming the graph is simple?
$endgroup$
– Servaes
5 hours ago
1
$begingroup$
Yes. That is assumed in the definition of graph that I learned. I learned to call a graph with loops or multiple edges between vertices a "multigraph."
$endgroup$
– Robert Shore
4 hours ago
add a comment |
$begingroup$
You are assuming the graph is simple?
$endgroup$
– Servaes
5 hours ago
1
$begingroup$
Yes. That is assumed in the definition of graph that I learned. I learned to call a graph with loops or multiple edges between vertices a "multigraph."
$endgroup$
– Robert Shore
4 hours ago
$begingroup$
You are assuming the graph is simple?
$endgroup$
– Servaes
5 hours ago
$begingroup$
You are assuming the graph is simple?
$endgroup$
– Servaes
5 hours ago
1
1
$begingroup$
Yes. That is assumed in the definition of graph that I learned. I learned to call a graph with loops or multiple edges between vertices a "multigraph."
$endgroup$
– Robert Shore
4 hours ago
$begingroup$
Yes. That is assumed in the definition of graph that I learned. I learned to call a graph with loops or multiple edges between vertices a "multigraph."
$endgroup$
– Robert Shore
4 hours ago
add a comment |
$begingroup$
Say graph is simple with no loops and that all vertices have different degree $d_1,d_2,...d_n$, then $${d_1,d_2,...d_n} = {0,1,2...,n-1}$$
So there is a vertex with degree $n-1$ and a vertex with degree $0$. A contradiction.
answered 9 hours ago
greedoidgreedoid
41k1149101
$endgroup$
$begingroup$
Perhaps it would be better to include that the graph is simple?
$endgroup$
– Shubham Johri
9 hours ago
$begingroup$
Is it necessary to specify "no loops"?
$endgroup$
– Shufflepants
4 hours ago
$begingroup$
Of course. Take a graph with two vertices and one connected to it self. @Shufflepants
$endgroup$
– greedoid
4 hours ago
1
$begingroup$
@greedoid Then by "no loops" did you mean "no self connection"? Otherwise I'd interpret "simple with no loops" as being equivalent to a tree. But in any case, the OP didn't specify "simple" or "no loops". So, it would seem the answer to the question is: it's not provable because it's not true.
$endgroup$
– Shufflepants
4 hours ago
1
$begingroup$
Because I didn't see it at first: This follows because in a simple graph the degree of any vertex must be less than the number of vertices. Thus if the vertex degrees are all different and less than $n$ they must be ${0, 1, 2..., n-1}$.
$endgroup$
– immibis
3 hours ago
|
show 1 more comment
$begingroup$
Say graph is simple with no loops and that all vertices have different degree $d_1,d_2,...d_n$, then $${d_1,d_2,...d_n} = {0,1,2...,n-1}$$
So there is a vertex with degree $n-1$ and a vertex with degree $0$. A contradiction.
answered 9 hours ago
greedoidgreedoid
41k1149101
$endgroup$
$begingroup$
Perhaps it would be better to include that the graph is simple?
$endgroup$
– Shubham Johri
9 hours ago
$begingroup$
Is it necessary to specify "no loops"?
$endgroup$
– Shufflepants
4 hours ago
$begingroup$
Of course. Take a graph with two vertices and one connected to it self. @Shufflepants
$endgroup$
– greedoid
4 hours ago
1
$begingroup$
@greedoid Then by "no loops" did you mean "no self connection"? Otherwise I'd interpret "simple with no loops" as being equivalent to a tree. But in any case, the OP didn't specify "simple" or "no loops". So, it would seem the answer to the question is: it's not provable because it's not true.
$endgroup$
– Shufflepants
4 hours ago
1
$begingroup$
Because I didn't see it at first: This follows because in a simple graph the degree of any vertex must be less than the number of vertices. Thus if the vertex degrees are all different and less than $n$ they must be ${0, 1, 2..., n-1}$.
$endgroup$
– immibis
3 hours ago
|
show 1 more comment
$begingroup$
Say graph is simple with no loops and that all vertices have different degree $d_1,d_2,...d_n$, then $${d_1,d_2,...d_n} = {0,1,2...,n-1}$$
So there is a vertex with degree $n-1$ and a vertex with degree $0$. A contradiction.
answered 9 hours ago
greedoidgreedoid
41k1149101
$endgroup$
Say graph is simple with no loops and that all vertices have different degree $d_1,d_2,...d_n$, then $${d_1,d_2,...d_n} = {0,1,2...,n-1}$$
So there is a vertex with degree $n-1$ and a vertex with degree $0$. A contradiction.
answered 9 hours ago
greedoidgreedoid
41k1149101
edited 9 hours ago
answered 9 hours ago
greedoidgreedoid
41k1149101
answered 9 hours ago
greedoidgreedoid
41k1149101
answered 9 hours ago
greedoidgreedoid
41k1149101
41k1149101
$begingroup$
Perhaps it would be better to include that the graph is simple?
$endgroup$
– Shubham Johri
9 hours ago
$begingroup$
Is it necessary to specify "no loops"?
$endgroup$
– Shufflepants
4 hours ago
$begingroup$
Of course. Take a graph with two vertices and one connected to it self. @Shufflepants
$endgroup$
– greedoid
4 hours ago
1
$begingroup$
@greedoid Then by "no loops" did you mean "no self connection"? Otherwise I'd interpret "simple with no loops" as being equivalent to a tree. But in any case, the OP didn't specify "simple" or "no loops". So, it would seem the answer to the question is: it's not provable because it's not true.
$endgroup$
– Shufflepants
4 hours ago
1
$begingroup$
Because I didn't see it at first: This follows because in a simple graph the degree of any vertex must be less than the number of vertices. Thus if the vertex degrees are all different and less than $n$ they must be ${0, 1, 2..., n-1}$.
$endgroup$
– immibis
3 hours ago
|
show 1 more comment
$begingroup$
Perhaps it would be better to include that the graph is simple?
$endgroup$
– Shubham Johri
9 hours ago
$begingroup$
Is it necessary to specify "no loops"?
$endgroup$
– Shufflepants
4 hours ago
$begingroup$
Of course. Take a graph with two vertices and one connected to it self. @Shufflepants
$endgroup$
– greedoid
4 hours ago
1
$begingroup$
@greedoid Then by "no loops" did you mean "no self connection"? Otherwise I'd interpret "simple with no loops" as being equivalent to a tree. But in any case, the OP didn't specify "simple" or "no loops". So, it would seem the answer to the question is: it's not provable because it's not true.
$endgroup$
– Shufflepants
4 hours ago
1
$begingroup$
Because I didn't see it at first: This follows because in a simple graph the degree of any vertex must be less than the number of vertices. Thus if the vertex degrees are all different and less than $n$ they must be ${0, 1, 2..., n-1}$.
$endgroup$
– immibis
3 hours ago
$begingroup$
Perhaps it would be better to include that the graph is simple?
$endgroup$
– Shubham Johri
9 hours ago
$begingroup$
Perhaps it would be better to include that the graph is simple?
$endgroup$
– Shubham Johri
9 hours ago
$begingroup$
Is it necessary to specify "no loops"?
$endgroup$
– Shufflepants
4 hours ago
$begingroup$
Is it necessary to specify "no loops"?
$endgroup$
– Shufflepants
4 hours ago
$begingroup$
Of course. Take a graph with two vertices and one connected to it self. @Shufflepants
$endgroup$
– greedoid
4 hours ago
$begingroup$
Of course. Take a graph with two vertices and one connected to it self. @Shufflepants
$endgroup$
– greedoid
4 hours ago
1
1
$begingroup$
@greedoid Then by "no loops" did you mean "no self connection"? Otherwise I'd interpret "simple with no loops" as being equivalent to a tree. But in any case, the OP didn't specify "simple" or "no loops". So, it would seem the answer to the question is: it's not provable because it's not true.
$endgroup$
– Shufflepants
4 hours ago
$begingroup$
@greedoid Then by "no loops" did you mean "no self connection"? Otherwise I'd interpret "simple with no loops" as being equivalent to a tree. But in any case, the OP didn't specify "simple" or "no loops". So, it would seem the answer to the question is: it's not provable because it's not true.
$endgroup$
– Shufflepants
4 hours ago
1
1
$begingroup$
Because I didn't see it at first: This follows because in a simple graph the degree of any vertex must be less than the number of vertices. Thus if the vertex degrees are all different and less than $n$ they must be ${0, 1, 2..., n-1}$.
$endgroup$
– immibis
3 hours ago
$begingroup$
Because I didn't see it at first: This follows because in a simple graph the degree of any vertex must be less than the number of vertices. Thus if the vertex degrees are all different and less than $n$ they must be ${0, 1, 2..., n-1}$.
$endgroup$
– immibis
3 hours ago
|
show 1 more comment
$begingroup$
Here is a counterexample.
Let $G$ be a graph on the positive integers where there is an edge from $x$ to $y$ if $x < y le 2x$. Note that we will ignore the direction of the edges. So $2$, for example, is neighbored by $1$, $3$, and $4$.
Let $j$ and $k$ be distinct positive integers. Without loss of generality assume that $j < k$. Note that $deg(j) = j + lfloor j/2 rfloor$ and $deg(k) = k + lfloor k/2 rfloor$. We have that
$$j < k$$
$$lfloor j/2 rfloor le lfloor k/2 rfloor$$
$$j + lfloor j/2 rfloor < k + lfloor k/2 rfloor$$
$$deg(j) < deg(k)$$
$$deg(j) neq deg(k)$$
Therefore, no two different vertices will have the same degree. $square$
answered 4 hours ago
PyRulezPyRulez
4,68622469
$endgroup$
$begingroup$
As noted at en.wikipedia.org/wiki/Graph_theory#Definitions, "V and E are usually taken to be finite, and many of the well-known results are not true (or are rather different) for infinite graphs because many of the arguments fail in the infinite case."
$endgroup$
– ruakh
3 mins ago
add a comment |
$begingroup$
Here is a counterexample.
Let $G$ be a graph on the positive integers where there is an edge from $x$ to $y$ if $x < y le 2x$. Note that we will ignore the direction of the edges. So $2$, for example, is neighbored by $1$, $3$, and $4$.
Let $j$ and $k$ be distinct positive integers. Without loss of generality assume that $j < k$. Note that $deg(j) = j + lfloor j/2 rfloor$ and $deg(k) = k + lfloor k/2 rfloor$. We have that
$$j < k$$
$$lfloor j/2 rfloor le lfloor k/2 rfloor$$
$$j + lfloor j/2 rfloor < k + lfloor k/2 rfloor$$
$$deg(j) < deg(k)$$
$$deg(j) neq deg(k)$$
Therefore, no two different vertices will have the same degree. $square$
answered 4 hours ago
PyRulezPyRulez
4,68622469
$endgroup$
$begingroup$
As noted at en.wikipedia.org/wiki/Graph_theory#Definitions, "V and E are usually taken to be finite, and many of the well-known results are not true (or are rather different) for infinite graphs because many of the arguments fail in the infinite case."
$endgroup$
– ruakh
3 mins ago
add a comment |
$begingroup$
Here is a counterexample.
Let $G$ be a graph on the positive integers where there is an edge from $x$ to $y$ if $x < y le 2x$. Note that we will ignore the direction of the edges. So $2$, for example, is neighbored by $1$, $3$, and $4$.
Let $j$ and $k$ be distinct positive integers. Without loss of generality assume that $j < k$. Note that $deg(j) = j + lfloor j/2 rfloor$ and $deg(k) = k + lfloor k/2 rfloor$. We have that
$$j < k$$
$$lfloor j/2 rfloor le lfloor k/2 rfloor$$
$$j + lfloor j/2 rfloor < k + lfloor k/2 rfloor$$
$$deg(j) < deg(k)$$
$$deg(j) neq deg(k)$$
Therefore, no two different vertices will have the same degree. $square$
answered 4 hours ago
PyRulezPyRulez
4,68622469
$endgroup$
Here is a counterexample.
Let $G$ be a graph on the positive integers where there is an edge from $x$ to $y$ if $x < y le 2x$. Note that we will ignore the direction of the edges. So $2$, for example, is neighbored by $1$, $3$, and $4$.
Let $j$ and $k$ be distinct positive integers. Without loss of generality assume that $j < k$. Note that $deg(j) = j + lfloor j/2 rfloor$ and $deg(k) = k + lfloor k/2 rfloor$. We have that
$$j < k$$
$$lfloor j/2 rfloor le lfloor k/2 rfloor$$
$$j + lfloor j/2 rfloor < k + lfloor k/2 rfloor$$
$$deg(j) < deg(k)$$
$$deg(j) neq deg(k)$$
Therefore, no two different vertices will have the same degree. $square$
answered 4 hours ago
PyRulezPyRulez
4,68622469
answered 4 hours ago
PyRulezPyRulez
4,68622469
answered 4 hours ago
PyRulezPyRulez
4,68622469
answered 4 hours ago
PyRulezPyRulez
4,68622469
4,68622469
$begingroup$
As noted at en.wikipedia.org/wiki/Graph_theory#Definitions, "V and E are usually taken to be finite, and many of the well-known results are not true (or are rather different) for infinite graphs because many of the arguments fail in the infinite case."
$endgroup$
– ruakh
3 mins ago
add a comment |
$begingroup$
As noted at en.wikipedia.org/wiki/Graph_theory#Definitions, "V and E are usually taken to be finite, and many of the well-known results are not true (or are rather different) for infinite graphs because many of the arguments fail in the infinite case."
$endgroup$
– ruakh
3 mins ago
$begingroup$
As noted at en.wikipedia.org/wiki/Graph_theory#Definitions, "V and E are usually taken to be finite, and many of the well-known results are not true (or are rather different) for infinite graphs because many of the arguments fail in the infinite case."
$endgroup$
– ruakh
3 mins ago
$begingroup$
As noted at en.wikipedia.org/wiki/Graph_theory#Definitions, "V and E are usually taken to be finite, and many of the well-known results are not true (or are rather different) for infinite graphs because many of the arguments fail in the infinite case."
$endgroup$
– ruakh
3 mins ago
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%2f3100174%2fhow-to-prove-that-at-least-two-vertices-have-the-same-degree-in-any-graph%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
1
$begingroup$
Please try to make the titles of your questions more informative. For example, Why does $a<b$ imply $a+c<b+c$? is much more useful for other users than A question about inequality. From How can I ask a good question?: Make your title as descriptive as possible. In many cases one can actually phrase the title as the question, at least in such a way so as to be comprehensible to an expert reader. You can find more tips for choosing a good title here.
$endgroup$
– Shaun
9 hours ago
1
$begingroup$
Symmetric, simple graphs?
$endgroup$
– Mindlack
9 hours ago
2
$begingroup$
Possible duplicate of "In a party people shake hands with one another"
$endgroup$
– JMoravitz
9 hours ago
$begingroup$
Possible duplicate of If n is a natural number ≥2 how do I prove that any graph with n vertices has at least two vertices of the same degree?
$endgroup$
– Acccumulation
4 hours ago