Hjdcti

How could an airship be repaired midflight?

Are Roman Catholic priests ever addressed as pastor

Can I use USB data pins as power source

Is it normal that my co-workers at a fitness company criticize my food choices?

Why one should not leave fingerprints on bulbs and plugs?

What is "focus distance lower/upper" and how is it different from depth of field?

I got the following comment from a reputed math journal. What does it mean?

Is a party consisting of only a bard, a cleric, and a warlock functional long-term?

Fastest way to pop N items from a large dict

A formula for delta function in quantum mechanics

Problem with FindRoot

Most cost effective thermostat setting: consistent temperature vs. lowest temperature possible

Do the common programs (for example: "ls", "cat") in Linux and BSD come from the same source code?

How difficult is it to simply disable/disengage the MCAS on Boeing 737 Max 8 & 9 Aircraft?

My adviser wants to be the first author

Unexpected result from ArcLength

How do I hide Chekhov's Gun?

Min function accepting varying number of arguments in C++17

Why Choose Less Effective Armour Types?

Is "upgrade" the right word to use in this context?

What is the adequate fee for a reveal operation?

Did Ender ever learn that he killed Stilson and/or Bonzo?

Draw saving money pig (Piggy Bank)

How to solve this challenging limit?

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

4

1

$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

share|cite|improve this question

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

add a comment | 

4

1

$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

share|cite|improve this question

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

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

share|cite|improve this question

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

share|cite|improve this question

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

share|cite|improve this question

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

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

asked 4 hours ago

Alex FreemanAlex Freeman

263

2 Answers
2

active

oldest

votes

2

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

share|cite|improve this answer

answered 3 hours ago

MauveMauve

1,5863516

$endgroup$

add a comment | 

0

$begingroup$

I kept working on it and realized I was wrong. This is my proof now, can anyone check it?

share|cite|improve this answer

answered 3 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
  3 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Ok, thanks! Everything else is correct?
  $endgroup$
  – Alex Freeman
  3 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
  3 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
  3 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I'm a little confused. Why do you assert we have $d(1)>0$?
  $endgroup$
  – Mauve
  2 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.

draft saved

draft discarded

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

Name

Email

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

Name

Email

Required, but never shown

2

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

share|cite|improve this answer

answered 3 hours ago

MauveMauve

1,5863516

$endgroup$

add a comment | 

2

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

share|cite|improve this answer

answered 3 hours ago

MauveMauve

1,5863516

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

share|cite|improve this answer

answered 3 hours ago

MauveMauve

1,5863516

$endgroup$

share|cite|improve this answer

answered 3 hours ago

MauveMauve

1,5863516

answered 3 hours ago

MauveMauve

1,5863516

answered 3 hours ago

MauveMauve

1,5863516

0

$begingroup$

I kept working on it and realized I was wrong. This is my proof now, can anyone check it?

share|cite|improve this answer

answered 3 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
  3 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Ok, thanks! Everything else is correct?
  $endgroup$
  – Alex Freeman
  3 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
  3 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
  3 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I'm a little confused. Why do you assert we have $d(1)>0$?
  $endgroup$
  – Mauve
  2 hours ago
  
  

  
  
  
  

add a comment | 

0

$begingroup$

I kept working on it and realized I was wrong. This is my proof now, can anyone check it?

share|cite|improve this answer

answered 3 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
  3 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Ok, thanks! Everything else is correct?
  $endgroup$
  – Alex Freeman
  3 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
  3 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
  3 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I'm a little confused. Why do you assert we have $d(1)>0$?
  $endgroup$
  – Mauve
  2 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?

share|cite|improve this answer

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

share|cite|improve this answer

answered 3 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 3 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 3 hours ago

Alex FreemanAlex Freeman

263