How to prove that at least two vertices have the same degree in any graph?












6












$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







share|cite|improve this question











$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


















6












$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







share|cite|improve this question











$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
















6












6








6


1



$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







share|cite|improve this question











$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






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited 3 hours ago









James Rettie

31




31










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
















  • 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












3 Answers
3






active

oldest

votes


















10












$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.






share|cite|improve this answer








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



















10












$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.






share|cite|improve this answer











$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





















0












$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$






share|cite|improve this answer









$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











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


















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









10












$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.






share|cite|improve this answer








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
















10












$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.






share|cite|improve this answer








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














10












10








10





$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.






share|cite|improve this answer








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.







share|cite|improve this answer








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.









share|cite|improve this answer



share|cite|improve this answer






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




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


















  • $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











10












$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.






share|cite|improve this answer











$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


















10












$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.






share|cite|improve this answer











$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
















10












10








10





$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.






share|cite|improve this answer











$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.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited 9 hours ago

























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




















  • $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













0












$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$






share|cite|improve this answer









$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
















0












$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$






share|cite|improve this answer









$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














0












0








0





$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$






share|cite|improve this answer









$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$







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










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


















  • $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


















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














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





















































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







-

Popular posts from this blog

How to reconfigure Docker Trusted Registry 2.x.x to use CEPH FS mount instead of NFS and other traditional...

Image
0 I am having trouble trying to reconfigure my DTR container to try and use a CEPH FS mount we created to act as a storage backend for our image repository. The Docs are very vague on this and nothing exactly explains on how to do it. Has anyone yet connected the dots? linux filesystems mount storage docker share | improve this question asked Feb 1 at 6:40 jRapp3r jRapp3r 1 1 add a comment  | 
Read more

is 'sed' thread safe

Image
2 If I have a shell/python script that uses sed to modify a file in place based on user inputs, and then two users run the same script at the same time or approx. same time, is 'sed' thread safe ? Or perhaps it is not an issue because the file_descripor that was opened by the first thread will be used to lock the file anyway ? thx linux sed python share | improve this question edited 7 hours ago Jeff Schaller 42.9k 11 59 137 asked 7 hours ago terreys terreys
Read more

How to make a Squid Proxy server?

Image
1 I want to set up squid proxy server for monitoring user activity in a network and Internet Web URL filtering for user. I also want to configure the user login, user log, user access group, and block unwanted web sites in my network. Please help me and guide me the full process to do this. server proxy squid share | improve this question edited Jul 31 '12 at 14:45 Jorge Castro 37.1k 107 422 617 asked Jul 31 '12 at 5:16 Goivind Tiwari Goivind Tiwari
Read more