Graph Theory - degree of vertices in a simple graphGraph Theory: Tree has at least 2 vertices of degree 1Graph Theory: Show that if G is a tree with the maximum degree >=k, then G has at least k vertices of degree 1.Graph Theory: labelled treeGraph Theory and verticesMaximal number of vertices in simple undirected graphShowing that a finite simple graph has at least two vertices with the same degreeprove graph G with n vertices, vertex of degree $n-1$ and rest of the vertices of degree $1$ is a tree graphSum of the vertex degrees for vertices of degree greater than $1$ in a treeGraph Theory - Degree of vertices proofProving that in a simple graph with $n$ vertices, two vertices have the same degree
Bacteria contamination inside a thermos bottle
Why did it take so long to abandon sail after steamships were demonstrated?
Are Roman Catholic priests ever addressed as pastor
What is the adequate fee for a reveal operation?
Recruiter wants very extensive technical details about all of my previous work
Simplify an interface for flexibly applying rules to periods of time
Why Choose Less Effective Armour Types?
If I can solve Sudoku, can I solve the Travelling Salesman Problem (TSP)? If so, how?
Official degrees of earth’s rotation per day
ERC721: How to get the owned tokens of an address
How could an airship be repaired midflight?
Employee lack of ownership
Brexit - No Deal Rejection
Do I need to be arrogant to get ahead?
Numerical Minimization of Large Expression
This word with a lot of past tenses
Did Ender ever learn that he killed Stilson and/or Bonzo?
How to explain that I do not want to visit a country due to personal safety concern?
How to make healing in an exploration game interesting
Have the tides ever turned twice on any open problem?
Professor being mistaken for a grad student
How to plot polar formed complex numbers?
Why does overlay work only on the first tcolorbox?
Pauli exclusion principle
Graph Theory - degree of vertices in a simple graph
Graph Theory: Tree has at least 2 vertices of degree 1Graph Theory: Show that if G is a tree with the maximum degree >=k, then G has at least k vertices of degree 1.Graph Theory: labelled treeGraph Theory and verticesMaximal number of vertices in simple undirected graphShowing that a finite simple graph has at least two vertices with the same degreeprove graph G with n vertices, vertex of degree $n-1$ and rest of the vertices of degree $1$ is a tree graphSum of the vertex degrees for vertices of degree greater than $1$ in a treeGraph Theory - Degree of vertices proofProving that in a simple graph with $n$ vertices, two vertices have the same degree
$begingroup$
"Let G be a simple graph. Either prove there are two vertices of G with the same degree or find an example where all vertices have a different degree."
So, here is what I thought. A simple graph can be a tree that we can build by increasing by 1 the degree of each vertex compared to everything else. However, I don't know how to express it as an example because we will have a graph that is infinite.
Can anyone help me with that? Or, can someone put the basis for the proof?
Any help is very much appreciated.
graph-theory
asked 5 hours ago
Alex FreemanAlex Freeman
263
New contributor
Alex Freeman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
"Let G be a simple graph. Either prove there are two vertices of G with the same degree or find an example where all vertices have a different degree."
So, here is what I thought. A simple graph can be a tree that we can build by increasing by 1 the degree of each vertex compared to everything else. However, I don't know how to express it as an example because we will have a graph that is infinite.
Can anyone help me with that? Or, can someone put the basis for the proof?
Any help is very much appreciated.
graph-theory
asked 5 hours ago
Alex FreemanAlex Freeman
263
New contributor
Alex Freeman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
"Let G be a simple graph. Either prove there are two vertices of G with the same degree or find an example where all vertices have a different degree."
So, here is what I thought. A simple graph can be a tree that we can build by increasing by 1 the degree of each vertex compared to everything else. However, I don't know how to express it as an example because we will have a graph that is infinite.
Can anyone help me with that? Or, can someone put the basis for the proof?
Any help is very much appreciated.
graph-theory
asked 5 hours ago
Alex FreemanAlex Freeman
263
New contributor
Alex Freeman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
"Let G be a simple graph. Either prove there are two vertices of G with the same degree or find an example where all vertices have a different degree."
So, here is what I thought. A simple graph can be a tree that we can build by increasing by 1 the degree of each vertex compared to everything else. However, I don't know how to express it as an example because we will have a graph that is infinite.
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 5 hours ago
Alex FreemanAlex Freeman
263
New contributor
Alex Freeman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 5 hours ago
Alex FreemanAlex Freeman
263
New contributor
Alex Freeman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 5 hours ago
Alex FreemanAlex Freeman
263
New contributor
Alex Freeman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 5 hours ago
Alex FreemanAlex Freeman
263
asked 5 hours ago
Alex FreemanAlex Freeman
263
263
New contributor
Alex Freeman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Alex Freeman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Alex Freeman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
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 4 hours ago
MauveMauve
1,5963516
$endgroup$
add a comment |
$begingroup$
I kept working on it and realized I was wrong. This is my proof now, can anyone check it?
answered 4 hours ago
Alex FreemanAlex Freeman
263
New contributor
Alex Freeman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
1
$begingroup$
You've neglected that a vertex can have degree $0$.
$endgroup$
– Mauve
4 hours ago
$begingroup$
Ok, thanks! Everything else is correct?
$endgroup$
– Alex Freeman
4 hours ago
1
$begingroup$
Your argument about forcing $d(n)=d(n-1)$ doesn't work once you add $0$ as a possible degree, since you could [possibly] have $d(1)=0, d(2)=1, ldots, d(n)=n-1$. However, there is a contradiction that would arise in this situation. Can you spot it?
$endgroup$
– Mauve
4 hours ago
$begingroup$
The contradiction is when we have d(1) = 0. But, because we said that d(1) > 0, we must have a number k s.t. d(1) = k > 0. This would mean that for d(n) = k +d(n-1). But, by properties, the max possible degree is n-1.
$endgroup$
– Alex Freeman
4 hours ago
$begingroup$
I'm a little confused. Why do you assert we have $d(1)>0$?
$endgroup$
– Mauve
3 hours 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
);
);
Alex Freeman is a new contributor. Be nice, and check out our Code of Conduct.
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%2f3150466%2fgraph-theory-degree-of-vertices-in-a-simple-graph%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
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 4 hours ago
MauveMauve
1,5963516
$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 4 hours ago
MauveMauve
1,5963516
$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 4 hours ago
MauveMauve
1,5963516
$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 4 hours ago
MauveMauve
1,5963516
answered 4 hours ago
MauveMauve
1,5963516
answered 4 hours ago
MauveMauve
1,5963516
answered 4 hours ago
MauveMauve
1,5963516
1,5963516
add a comment |
add a comment |
$begingroup$
I kept working on it and realized I was wrong. This is my proof now, can anyone check it?
answered 4 hours ago
Alex FreemanAlex Freeman
263
New contributor
Alex Freeman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
1
$begingroup$
You've neglected that a vertex can have degree $0$.
$endgroup$
– Mauve
4 hours ago
$begingroup$
Ok, thanks! Everything else is correct?
$endgroup$
– Alex Freeman
4 hours ago
1
$begingroup$
Your argument about forcing $d(n)=d(n-1)$ doesn't work once you add $0$ as a possible degree, since you could [possibly] have $d(1)=0, d(2)=1, ldots, d(n)=n-1$. However, there is a contradiction that would arise in this situation. Can you spot it?
$endgroup$
– Mauve
4 hours ago
$begingroup$
The contradiction is when we have d(1) = 0. But, because we said that d(1) > 0, we must have a number k s.t. d(1) = k > 0. This would mean that for d(n) = k +d(n-1). But, by properties, the max possible degree is n-1.
$endgroup$
– Alex Freeman
4 hours ago
$begingroup$
I'm a little confused. Why do you assert we have $d(1)>0$?
$endgroup$
– Mauve
3 hours ago
add a comment |
$begingroup$
I kept working on it and realized I was wrong. This is my proof now, can anyone check it?
answered 4 hours ago
Alex FreemanAlex Freeman
263
New contributor
Alex Freeman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
1
$begingroup$
You've neglected that a vertex can have degree $0$.
$endgroup$
– Mauve
4 hours ago
$begingroup$
Ok, thanks! Everything else is correct?
$endgroup$
– Alex Freeman
4 hours ago
1
$begingroup$
Your argument about forcing $d(n)=d(n-1)$ doesn't work once you add $0$ as a possible degree, since you could [possibly] have $d(1)=0, d(2)=1, ldots, d(n)=n-1$. However, there is a contradiction that would arise in this situation. Can you spot it?
$endgroup$
– Mauve
4 hours ago
$begingroup$
The contradiction is when we have d(1) = 0. But, because we said that d(1) > 0, we must have a number k s.t. d(1) = k > 0. This would mean that for d(n) = k +d(n-1). But, by properties, the max possible degree is n-1.
$endgroup$
– Alex Freeman
4 hours ago
$begingroup$
I'm a little confused. Why do you assert we have $d(1)>0$?
$endgroup$
– Mauve
3 hours ago
add a comment |
$begingroup$
I kept working on it and realized I was wrong. This is my proof now, can anyone check it?
answered 4 hours ago
Alex FreemanAlex Freeman
263
New contributor
Alex Freeman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
I kept working on it and realized I was wrong. This is my proof now, can anyone check it?
answered 4 hours ago
Alex FreemanAlex Freeman
263
New contributor
Alex Freeman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered 4 hours ago
Alex FreemanAlex Freeman
263
New contributor
Alex Freeman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered 4 hours ago
Alex FreemanAlex Freeman
263
answered 4 hours ago
Alex FreemanAlex Freeman
263
263
New contributor
Alex Freeman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Alex Freeman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Alex Freeman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
1
$begingroup$
You've neglected that a vertex can have degree $0$.
$endgroup$
– Mauve
4 hours ago
$begingroup$
Ok, thanks! Everything else is correct?
$endgroup$
– Alex Freeman
4 hours ago
1
$begingroup$
Your argument about forcing $d(n)=d(n-1)$ doesn't work once you add $0$ as a possible degree, since you could [possibly] have $d(1)=0, d(2)=1, ldots, d(n)=n-1$. However, there is a contradiction that would arise in this situation. Can you spot it?
$endgroup$
– Mauve
4 hours ago
$begingroup$
The contradiction is when we have d(1) = 0. But, because we said that d(1) > 0, we must have a number k s.t. d(1) = k > 0. This would mean that for d(n) = k +d(n-1). But, by properties, the max possible degree is n-1.
$endgroup$
– Alex Freeman
4 hours ago
$begingroup$
I'm a little confused. Why do you assert we have $d(1)>0$?
$endgroup$
– Mauve
3 hours ago
add a comment |
1
$begingroup$
You've neglected that a vertex can have degree $0$.
$endgroup$
– Mauve
4 hours ago
$begingroup$
Ok, thanks! Everything else is correct?
$endgroup$
– Alex Freeman
4 hours ago
1
$begingroup$
Your argument about forcing $d(n)=d(n-1)$ doesn't work once you add $0$ as a possible degree, since you could [possibly] have $d(1)=0, d(2)=1, ldots, d(n)=n-1$. However, there is a contradiction that would arise in this situation. Can you spot it?
$endgroup$
– Mauve
4 hours ago
$begingroup$
The contradiction is when we have d(1) = 0. But, because we said that d(1) > 0, we must have a number k s.t. d(1) = k > 0. This would mean that for d(n) = k +d(n-1). But, by properties, the max possible degree is n-1.
$endgroup$
– Alex Freeman
4 hours ago
$begingroup$
I'm a little confused. Why do you assert we have $d(1)>0$?
$endgroup$
– Mauve
3 hours ago
1
1
$begingroup$
You've neglected that a vertex can have degree $0$.
$endgroup$
– Mauve
4 hours ago
$begingroup$
You've neglected that a vertex can have degree $0$.
$endgroup$
– Mauve
4 hours ago
$begingroup$
Ok, thanks! Everything else is correct?
$endgroup$
– Alex Freeman
4 hours ago
$begingroup$
Ok, thanks! Everything else is correct?
$endgroup$
– Alex Freeman
4 hours ago
1
1
$begingroup$
Your argument about forcing $d(n)=d(n-1)$ doesn't work once you add $0$ as a possible degree, since you could [possibly] have $d(1)=0, d(2)=1, ldots, d(n)=n-1$. However, there is a contradiction that would arise in this situation. Can you spot it?
$endgroup$
– Mauve
4 hours ago
$begingroup$
Your argument about forcing $d(n)=d(n-1)$ doesn't work once you add $0$ as a possible degree, since you could [possibly] have $d(1)=0, d(2)=1, ldots, d(n)=n-1$. However, there is a contradiction that would arise in this situation. Can you spot it?
$endgroup$
– Mauve
4 hours ago
$begingroup$
The contradiction is when we have d(1) = 0. But, because we said that d(1) > 0, we must have a number k s.t. d(1) = k > 0. This would mean that for d(n) = k +d(n-1). But, by properties, the max possible degree is n-1.
$endgroup$
– Alex Freeman
4 hours ago
$begingroup$
The contradiction is when we have d(1) = 0. But, because we said that d(1) > 0, we must have a number k s.t. d(1) = k > 0. This would mean that for d(n) = k +d(n-1). But, by properties, the max possible degree is n-1.
$endgroup$
– Alex Freeman
4 hours ago
$begingroup$
I'm a little confused. Why do you assert we have $d(1)>0$?
$endgroup$
– Mauve
3 hours ago
$begingroup$
I'm a little confused. Why do you assert we have $d(1)>0$?
$endgroup$
– Mauve
3 hours ago
add a comment |
Alex Freeman is a new contributor. Be nice, and check out our Code of Conduct.
Alex Freeman is a new contributor. Be nice, and check out our Code of Conduct.
Alex Freeman is a new contributor. Be nice, and check out our Code of Conduct.
Alex Freeman is a new contributor. Be nice, and check out our Code of Conduct.
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%2f3150466%2fgraph-theory-degree-of-vertices-in-a-simple-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
