degree of vertices in G [on hold]
Clash Royale CLAN TAG#URR8PPP
$begingroup$
Prove there are two vertices of G with the same degree.
Can anyone help me with that? Or, can someone put the basis for the proof?
Any help is very much appreciated.
graph-theory
asked Mar 16 at 14:51
Alex FreemanAlex Freeman
155
$endgroup$
put on hold as off-topic by Alexander Gruber♦ Apr 11 at 16:23
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Alexander Gruber
add a comment |
$begingroup$
Prove there are two vertices of G with the same degree.
Can anyone help me with that? Or, can someone put the basis for the proof?
Any help is very much appreciated.
graph-theory
asked Mar 16 at 14:51
Alex FreemanAlex Freeman
155
$endgroup$
put on hold as off-topic by Alexander Gruber♦ Apr 11 at 16:23
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Alexander Gruber
add a comment |
$begingroup$
Prove there are two vertices of G with the same degree.
Can anyone help me with that? Or, can someone put the basis for the proof?
Any help is very much appreciated.
graph-theory
asked Mar 16 at 14:51
Alex FreemanAlex Freeman
155
$endgroup$
Prove there are two vertices of G with the same degree.
Can anyone help me with that? Or, can someone put the basis for the proof?
Any help is very much appreciated.
graph-theory
graph-theory
asked Mar 16 at 14:51
Alex FreemanAlex Freeman
155
asked Mar 16 at 14:51
Alex FreemanAlex Freeman
155
edited Apr 3 at 15:51
Alex Freeman
asked Mar 16 at 14:51
Alex FreemanAlex Freeman
155
asked Mar 16 at 14:51
Alex FreemanAlex Freeman
155
asked Mar 16 at 14:51
Alex FreemanAlex Freeman
155
155
put on hold as off-topic by Alexander Gruber♦ Apr 11 at 16:23
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Alexander Gruber
put on hold as off-topic by Alexander Gruber♦ Apr 11 at 16:23
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Alexander Gruber
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Hint: In a simple graph $G=(V, E)$ on $n$ vertices, the maximum degree of a vertex is $n-1$. In particular, the set of possible degrees is $A := 0, 1, ldots, n-1$, and has cardinality $n$. Now suppose that each vertex in your graph $G$ has a distinct degree. Then we can define an injection
$$phi: V rightarrow A$$
$$v mapsto deg(v).$$
But $V$ and $A$ have the same cardinality, so injectivity actually implies ___________.
Now note that the only way for a vertex to have degree $n-1$ is if it is adjacent to all other vertices in the graph. Can you find a contradiction?
answered Mar 16 at 16:04
MauveMauve
1,6153516
$endgroup$
add a comment |
$begingroup$
Suppose all vertices have differnt degree. Then all the numebers $0,1,2,...,n-1$ apperas as degrees. But then there is a vertex (of degree $n-1$) which is connected to all vertices and including that one wit degree 0. A contradiction.
answered Mar 26 at 21:10
Maria MazurMaria Mazur
50k1361125
$endgroup$
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Hint: In a simple graph $G=(V, E)$ on $n$ vertices, the maximum degree of a vertex is $n-1$. In particular, the set of possible degrees is $A := 0, 1, ldots, n-1$, and has cardinality $n$. Now suppose that each vertex in your graph $G$ has a distinct degree. Then we can define an injection
$$phi: V rightarrow A$$
$$v mapsto deg(v).$$
But $V$ and $A$ have the same cardinality, so injectivity actually implies ___________.
Now note that the only way for a vertex to have degree $n-1$ is if it is adjacent to all other vertices in the graph. Can you find a contradiction?
answered Mar 16 at 16:04
MauveMauve
1,6153516
$endgroup$
add a comment |
$begingroup$
Hint: In a simple graph $G=(V, E)$ on $n$ vertices, the maximum degree of a vertex is $n-1$. In particular, the set of possible degrees is $A := 0, 1, ldots, n-1$, and has cardinality $n$. Now suppose that each vertex in your graph $G$ has a distinct degree. Then we can define an injection
$$phi: V rightarrow A$$
$$v mapsto deg(v).$$
But $V$ and $A$ have the same cardinality, so injectivity actually implies ___________.
Now note that the only way for a vertex to have degree $n-1$ is if it is adjacent to all other vertices in the graph. Can you find a contradiction?
answered Mar 16 at 16:04
MauveMauve
1,6153516
$endgroup$
add a comment |
$begingroup$
Hint: In a simple graph $G=(V, E)$ on $n$ vertices, the maximum degree of a vertex is $n-1$. In particular, the set of possible degrees is $A := 0, 1, ldots, n-1$, and has cardinality $n$. Now suppose that each vertex in your graph $G$ has a distinct degree. Then we can define an injection
$$phi: V rightarrow A$$
$$v mapsto deg(v).$$
But $V$ and $A$ have the same cardinality, so injectivity actually implies ___________.
Now note that the only way for a vertex to have degree $n-1$ is if it is adjacent to all other vertices in the graph. Can you find a contradiction?
answered Mar 16 at 16:04
MauveMauve
1,6153516
$endgroup$
Hint: In a simple graph $G=(V, E)$ on $n$ vertices, the maximum degree of a vertex is $n-1$. In particular, the set of possible degrees is $A := 0, 1, ldots, n-1$, and has cardinality $n$. Now suppose that each vertex in your graph $G$ has a distinct degree. Then we can define an injection
$$phi: V rightarrow A$$
$$v mapsto deg(v).$$
But $V$ and $A$ have the same cardinality, so injectivity actually implies ___________.
Now note that the only way for a vertex to have degree $n-1$ is if it is adjacent to all other vertices in the graph. Can you find a contradiction?
answered Mar 16 at 16:04
MauveMauve
1,6153516
answered Mar 16 at 16:04
MauveMauve
1,6153516
answered Mar 16 at 16:04
MauveMauve
1,6153516
answered Mar 16 at 16:04
MauveMauve
1,6153516
1,6153516
add a comment |
add a comment |
$begingroup$
Suppose all vertices have differnt degree. Then all the numebers $0,1,2,...,n-1$ apperas as degrees. But then there is a vertex (of degree $n-1$) which is connected to all vertices and including that one wit degree 0. A contradiction.
answered Mar 26 at 21:10
Maria MazurMaria Mazur
50k1361125
$endgroup$
add a comment |
$begingroup$
Suppose all vertices have differnt degree. Then all the numebers $0,1,2,...,n-1$ apperas as degrees. But then there is a vertex (of degree $n-1$) which is connected to all vertices and including that one wit degree 0. A contradiction.
answered Mar 26 at 21:10
Maria MazurMaria Mazur
50k1361125
$endgroup$
add a comment |
$begingroup$
Suppose all vertices have differnt degree. Then all the numebers $0,1,2,...,n-1$ apperas as degrees. But then there is a vertex (of degree $n-1$) which is connected to all vertices and including that one wit degree 0. A contradiction.
answered Mar 26 at 21:10
Maria MazurMaria Mazur
50k1361125
$endgroup$
Suppose all vertices have differnt degree. Then all the numebers $0,1,2,...,n-1$ apperas as degrees. But then there is a vertex (of degree $n-1$) which is connected to all vertices and including that one wit degree 0. A contradiction.
answered Mar 26 at 21:10
Maria MazurMaria Mazur
50k1361125
answered Mar 26 at 21:10
Maria MazurMaria Mazur
50k1361125
answered Mar 26 at 21:10
Maria MazurMaria Mazur
50k1361125
answered Mar 26 at 21:10
Maria MazurMaria Mazur
50k1361125
50k1361125
add a comment |
add a comment |