How to prove that at least two vertices have the same degree in any graph? [duplicate]
Clash Royale CLAN TAG#URR8PPP
$begingroup$
This question already has an answer here:
If $n$ is a natural number $ge 2$ how do I prove that any graph with $n$ vertices has at least two vertices of the same degree?
2 answers
“In a party people shake hands with one another”
3 answers
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
$endgroup$
marked as duplicate by JMoravitz, Mike Earnest, Servaes, Acccumulation, verret Feb 5 at 5:19
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
add a comment |
$begingroup$
This question already has an answer here:
If $n$ is a natural number $ge 2$ how do I prove that any graph with $n$ vertices has at least two vertices of the same degree?
2 answers
“In a party people shake hands with one another”
3 answers
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
$endgroup$
marked as duplicate by JMoravitz, Mike Earnest, Servaes, Acccumulation, verret Feb 5 at 5:19
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
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
Feb 4 at 17:56
1
$begingroup$
Symmetric, simple graphs?
$endgroup$
– Mindlack
Feb 4 at 17:56
1
$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
Feb 4 at 22:23
add a comment |
$begingroup$
This question already has an answer here:
If $n$ is a natural number $ge 2$ how do I prove that any graph with $n$ vertices has at least two vertices of the same degree?
2 answers
“In a party people shake hands with one another”
3 answers
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
$endgroup$
This question already has an answer here:
If $n$ is a natural number $ge 2$ how do I prove that any graph with $n$ vertices has at least two vertices of the same degree?
2 answers
“In a party people shake hands with one another”
3 answers
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?
This question already has an answer here:
If $n$ is a natural number $ge 2$ how do I prove that any graph with $n$ vertices has at least two vertices of the same degree?
2 answers
“In a party people shake hands with one another”
3 answers
combinatorics discrete-mathematics graph-theory
combinatorics discrete-mathematics graph-theory
edited Feb 5 at 0:00
James Rettie
31
31
asked Feb 4 at 17:52
desiignerdesiigner
675
675
marked as duplicate by JMoravitz, Mike Earnest, Servaes, Acccumulation, verret Feb 5 at 5:19
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
marked as duplicate by JMoravitz, Mike Earnest, Servaes, Acccumulation, verret Feb 5 at 5:19
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
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
Feb 4 at 17:56
1
$begingroup$
Symmetric, simple graphs?
$endgroup$
– Mindlack
Feb 4 at 17:56
1
$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
Feb 4 at 22:23
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
Feb 4 at 17:56
1
$begingroup$
Symmetric, simple graphs?
$endgroup$
– Mindlack
Feb 4 at 17:56
1
$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
Feb 4 at 22:23
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
Feb 4 at 17:56
$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
Feb 4 at 17:56
1
1
$begingroup$
Symmetric, simple graphs?
$endgroup$
– Mindlack
Feb 4 at 17:56
$begingroup$
Symmetric, simple graphs?
$endgroup$
– Mindlack
Feb 4 at 17:56
1
1
$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
Feb 4 at 22:23
$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
Feb 4 at 22:23
add a comment |
3 Answers
3
active
oldest
votes
$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.
$endgroup$
$begingroup$
Perhaps it would be better to include that the graph is simple?
$endgroup$
– Shubham Johri
Feb 4 at 18:04
$begingroup$
Is it necessary to specify "no loops"?
$endgroup$
– Shufflepants
Feb 4 at 22:24
$begingroup$
Of course. Take a graph with two vertices and one connected to it self. @Shufflepants
$endgroup$
– greedoid
Feb 4 at 22:25
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
Feb 4 at 22:32
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
Feb 5 at 0:02
|
show 1 more 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.
$endgroup$
$begingroup$
You are assuming the graph is simple?
$endgroup$
– Servaes
Feb 4 at 22:07
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
Feb 4 at 23:04
add a comment |
$begingroup$
EDIT: Graphs are typically defined as being finite. Infinite graphs are a generalization. I did not know this at the time of the post. I will leave this answer up though in case anyone finds it useful.
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$
$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
Feb 5 at 3:11
$begingroup$
@ruakh Huh, didn't know that. I edited a disclaimer into my answer.
$endgroup$
– PyRulez
Feb 5 at 3:44
add a comment |
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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.
$endgroup$
$begingroup$
Perhaps it would be better to include that the graph is simple?
$endgroup$
– Shubham Johri
Feb 4 at 18:04
$begingroup$
Is it necessary to specify "no loops"?
$endgroup$
– Shufflepants
Feb 4 at 22:24
$begingroup$
Of course. Take a graph with two vertices and one connected to it self. @Shufflepants
$endgroup$
– greedoid
Feb 4 at 22:25
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
Feb 4 at 22:32
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
Feb 5 at 0:02
|
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.
$endgroup$
$begingroup$
Perhaps it would be better to include that the graph is simple?
$endgroup$
– Shubham Johri
Feb 4 at 18:04
$begingroup$
Is it necessary to specify "no loops"?
$endgroup$
– Shufflepants
Feb 4 at 22:24
$begingroup$
Of course. Take a graph with two vertices and one connected to it self. @Shufflepants
$endgroup$
– greedoid
Feb 4 at 22:25
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
Feb 4 at 22:32
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
Feb 5 at 0:02
|
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.
$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.
edited Feb 4 at 18:06
answered Feb 4 at 17:57
greedoidgreedoid
44.6k1156111
44.6k1156111
$begingroup$
Perhaps it would be better to include that the graph is simple?
$endgroup$
– Shubham Johri
Feb 4 at 18:04
$begingroup$
Is it necessary to specify "no loops"?
$endgroup$
– Shufflepants
Feb 4 at 22:24
$begingroup$
Of course. Take a graph with two vertices and one connected to it self. @Shufflepants
$endgroup$
– greedoid
Feb 4 at 22:25
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
Feb 4 at 22:32
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
Feb 5 at 0:02
|
show 1 more comment
$begingroup$
Perhaps it would be better to include that the graph is simple?
$endgroup$
– Shubham Johri
Feb 4 at 18:04
$begingroup$
Is it necessary to specify "no loops"?
$endgroup$
– Shufflepants
Feb 4 at 22:24
$begingroup$
Of course. Take a graph with two vertices and one connected to it self. @Shufflepants
$endgroup$
– greedoid
Feb 4 at 22:25
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
Feb 4 at 22:32
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
Feb 5 at 0:02
$begingroup$
Perhaps it would be better to include that the graph is simple?
$endgroup$
– Shubham Johri
Feb 4 at 18:04
$begingroup$
Perhaps it would be better to include that the graph is simple?
$endgroup$
– Shubham Johri
Feb 4 at 18:04
$begingroup$
Is it necessary to specify "no loops"?
$endgroup$
– Shufflepants
Feb 4 at 22:24
$begingroup$
Is it necessary to specify "no loops"?
$endgroup$
– Shufflepants
Feb 4 at 22:24
$begingroup$
Of course. Take a graph with two vertices and one connected to it self. @Shufflepants
$endgroup$
– greedoid
Feb 4 at 22:25
$begingroup$
Of course. Take a graph with two vertices and one connected to it self. @Shufflepants
$endgroup$
– greedoid
Feb 4 at 22:25
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
Feb 4 at 22:32
$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
Feb 4 at 22:32
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
Feb 5 at 0:02
$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
Feb 5 at 0:02
|
show 1 more 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.
$endgroup$
$begingroup$
You are assuming the graph is simple?
$endgroup$
– Servaes
Feb 4 at 22:07
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
Feb 4 at 23:04
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.
$endgroup$
$begingroup$
You are assuming the graph is simple?
$endgroup$
– Servaes
Feb 4 at 22:07
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
Feb 4 at 23:04
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.
$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 Feb 4 at 17:59
Robert ShoreRobert Shore
1,59415
1,59415
$begingroup$
You are assuming the graph is simple?
$endgroup$
– Servaes
Feb 4 at 22:07
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
Feb 4 at 23:04
add a comment |
$begingroup$
You are assuming the graph is simple?
$endgroup$
– Servaes
Feb 4 at 22:07
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
Feb 4 at 23:04
$begingroup$
You are assuming the graph is simple?
$endgroup$
– Servaes
Feb 4 at 22:07
$begingroup$
You are assuming the graph is simple?
$endgroup$
– Servaes
Feb 4 at 22:07
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
Feb 4 at 23:04
$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
Feb 4 at 23:04
add a comment |
$begingroup$
EDIT: Graphs are typically defined as being finite. Infinite graphs are a generalization. I did not know this at the time of the post. I will leave this answer up though in case anyone finds it useful.
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$
$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
Feb 5 at 3:11
$begingroup$
@ruakh Huh, didn't know that. I edited a disclaimer into my answer.
$endgroup$
– PyRulez
Feb 5 at 3:44
add a comment |
$begingroup$
EDIT: Graphs are typically defined as being finite. Infinite graphs are a generalization. I did not know this at the time of the post. I will leave this answer up though in case anyone finds it useful.
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$
$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
Feb 5 at 3:11
$begingroup$
@ruakh Huh, didn't know that. I edited a disclaimer into my answer.
$endgroup$
– PyRulez
Feb 5 at 3:44
add a comment |
$begingroup$
EDIT: Graphs are typically defined as being finite. Infinite graphs are a generalization. I did not know this at the time of the post. I will leave this answer up though in case anyone finds it useful.
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$
$endgroup$
EDIT: Graphs are typically defined as being finite. Infinite graphs are a generalization. I did not know this at the time of the post. I will leave this answer up though in case anyone finds it useful.
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$
edited Feb 5 at 3:44
answered Feb 4 at 22:49
PyRulezPyRulez
4,94122470
4,94122470
$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
Feb 5 at 3:11
$begingroup$
@ruakh Huh, didn't know that. I edited a disclaimer into my answer.
$endgroup$
– PyRulez
Feb 5 at 3:44
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
Feb 5 at 3:11
$begingroup$
@ruakh Huh, didn't know that. I edited a disclaimer into my answer.
$endgroup$
– PyRulez
Feb 5 at 3:44
$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
Feb 5 at 3:11
$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
Feb 5 at 3:11
$begingroup$
@ruakh Huh, didn't know that. I edited a disclaimer into my answer.
$endgroup$
– PyRulez
Feb 5 at 3:44
$begingroup$
@ruakh Huh, didn't know that. I edited a disclaimer into my answer.
$endgroup$
– PyRulez
Feb 5 at 3:44
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
Feb 4 at 17:56
1
$begingroup$
Symmetric, simple graphs?
$endgroup$
– Mindlack
Feb 4 at 17:56
1
$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
Feb 4 at 22:23