Determine if a graph exists knowing the degree of its vertices












5












$begingroup$



Problem: There is a graph on ten vertices whose degrees are $9,8,8,8,6,5,4,4,2,2$




Answer: False.



My attempt: Since we know that $2 | E | = sum _ { v in V } d ( v )$, $$2cdot 28 = 9+8cdot3+6+5+4cdot2+2cdot2$$
Hence $| E | = 28$. Since we don't now more about the graph (it may not be a tree), how can I determine that such graph does not exist?










share|cite|improve this question











$endgroup$








  • 1




    $begingroup$
    Is that a simple graph?
    $endgroup$
    – greedoid
    Jan 21 at 17:25






  • 1




    $begingroup$
    @greedoid The professor didn't precise but since we only studied simple graph this semester I assume it is.
    $endgroup$
    – NotAbelianGroup
    Jan 21 at 17:26
















5












$begingroup$



Problem: There is a graph on ten vertices whose degrees are $9,8,8,8,6,5,4,4,2,2$




Answer: False.



My attempt: Since we know that $2 | E | = sum _ { v in V } d ( v )$, $$2cdot 28 = 9+8cdot3+6+5+4cdot2+2cdot2$$
Hence $| E | = 28$. Since we don't now more about the graph (it may not be a tree), how can I determine that such graph does not exist?










share|cite|improve this question











$endgroup$








  • 1




    $begingroup$
    Is that a simple graph?
    $endgroup$
    – greedoid
    Jan 21 at 17:25






  • 1




    $begingroup$
    @greedoid The professor didn't precise but since we only studied simple graph this semester I assume it is.
    $endgroup$
    – NotAbelianGroup
    Jan 21 at 17:26














5












5








5


1



$begingroup$



Problem: There is a graph on ten vertices whose degrees are $9,8,8,8,6,5,4,4,2,2$




Answer: False.



My attempt: Since we know that $2 | E | = sum _ { v in V } d ( v )$, $$2cdot 28 = 9+8cdot3+6+5+4cdot2+2cdot2$$
Hence $| E | = 28$. Since we don't now more about the graph (it may not be a tree), how can I determine that such graph does not exist?










share|cite|improve this question











$endgroup$





Problem: There is a graph on ten vertices whose degrees are $9,8,8,8,6,5,4,4,2,2$




Answer: False.



My attempt: Since we know that $2 | E | = sum _ { v in V } d ( v )$, $$2cdot 28 = 9+8cdot3+6+5+4cdot2+2cdot2$$
Hence $| E | = 28$. Since we don't now more about the graph (it may not be a tree), how can I determine that such graph does not exist?







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 Jan 21 at 17:55









greedoid

39.7k114798




39.7k114798










asked Jan 21 at 17:21









NotAbelianGroupNotAbelianGroup

15511




15511








  • 1




    $begingroup$
    Is that a simple graph?
    $endgroup$
    – greedoid
    Jan 21 at 17:25






  • 1




    $begingroup$
    @greedoid The professor didn't precise but since we only studied simple graph this semester I assume it is.
    $endgroup$
    – NotAbelianGroup
    Jan 21 at 17:26














  • 1




    $begingroup$
    Is that a simple graph?
    $endgroup$
    – greedoid
    Jan 21 at 17:25






  • 1




    $begingroup$
    @greedoid The professor didn't precise but since we only studied simple graph this semester I assume it is.
    $endgroup$
    – NotAbelianGroup
    Jan 21 at 17:26








1




1




$begingroup$
Is that a simple graph?
$endgroup$
– greedoid
Jan 21 at 17:25




$begingroup$
Is that a simple graph?
$endgroup$
– greedoid
Jan 21 at 17:25




1




1




$begingroup$
@greedoid The professor didn't precise but since we only studied simple graph this semester I assume it is.
$endgroup$
– NotAbelianGroup
Jan 21 at 17:26




$begingroup$
@greedoid The professor didn't precise but since we only studied simple graph this semester I assume it is.
$endgroup$
– NotAbelianGroup
Jan 21 at 17:26










2 Answers
2






active

oldest

votes


















7












$begingroup$

Suppose it is simple and without loops.



If that one exist then if we delete node with degree $9$ and it edges, we would get a graph:



$$7,7,7,5,4,3,3,1,1$$



now if we delete node of degree $7$ and it edges we get



$$6,6,4,3,2,2,1,0;;;;{rm or} ;;;;geq 6,?,?,?,?,?,0,0$$



Second situation is impossible since at least one node of degree $0$ must be connected with first one with degree at least 6.



So suppose 1. situation is possible, then it is also: $$5,3,2,1,1,0$$



but this is actualy impossible (since at least one node of degree $0$ must be connected with first one with degree at least 5).



So such a graph does not exist.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    Perfect thank you very much.
    $endgroup$
    – NotAbelianGroup
    Jan 21 at 18:04



















5












$begingroup$

The answer is FALSE.



We proceed with the Havel–Hakimi Theorem, which determines whether a degree sequence can represent a simple graph.



Applying this theorem, we note that the original degree sequence is graphical if and only if the degree sequence given by ${7, 7, 7, 5, 4, 3, 3, 2, 1}$ is graphical. We can keep on reiterating to get the following degree lists:



$${6, 6, 4, 3, 2, 2, 1, 0} rightarrow {5, 3, 2, 1, 1, 0, 0} rightarrow {2, 1, 0, 0, 0, -1}$$



But, the last degree list is clearly not graphical: it has an edge with a negative degree! So, the answer is false.






share|cite|improve this answer











$endgroup$









  • 2




    $begingroup$
    Well, the given answer by the OP is "false" and thereby not false, :)
    $endgroup$
    – Hagen von Eitzen
    Jan 21 at 19:32






  • 1




    $begingroup$
    Are you sure you've applied the algorithm correctly (drop highest number $k$, subtract 1 from the next $k$ numbers, re-sort)? I get ${6,6,4,3,2,2,1,0}, {5,3,2,1,1,0,0}, {2,1,0,0,0,-1}$.
    $endgroup$
    – Paul Sinclair
    Jan 21 at 20:48












  • $begingroup$
    Oops, you are right. I just edited my post @PaulSinclair
    $endgroup$
    – Ekesh Kumar
    Jan 21 at 21:28











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%2f3082125%2fdetermine-if-a-graph-exists-knowing-the-degree-of-its-vertices%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









7












$begingroup$

Suppose it is simple and without loops.



If that one exist then if we delete node with degree $9$ and it edges, we would get a graph:



$$7,7,7,5,4,3,3,1,1$$



now if we delete node of degree $7$ and it edges we get



$$6,6,4,3,2,2,1,0;;;;{rm or} ;;;;geq 6,?,?,?,?,?,0,0$$



Second situation is impossible since at least one node of degree $0$ must be connected with first one with degree at least 6.



So suppose 1. situation is possible, then it is also: $$5,3,2,1,1,0$$



but this is actualy impossible (since at least one node of degree $0$ must be connected with first one with degree at least 5).



So such a graph does not exist.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    Perfect thank you very much.
    $endgroup$
    – NotAbelianGroup
    Jan 21 at 18:04
















7












$begingroup$

Suppose it is simple and without loops.



If that one exist then if we delete node with degree $9$ and it edges, we would get a graph:



$$7,7,7,5,4,3,3,1,1$$



now if we delete node of degree $7$ and it edges we get



$$6,6,4,3,2,2,1,0;;;;{rm or} ;;;;geq 6,?,?,?,?,?,0,0$$



Second situation is impossible since at least one node of degree $0$ must be connected with first one with degree at least 6.



So suppose 1. situation is possible, then it is also: $$5,3,2,1,1,0$$



but this is actualy impossible (since at least one node of degree $0$ must be connected with first one with degree at least 5).



So such a graph does not exist.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    Perfect thank you very much.
    $endgroup$
    – NotAbelianGroup
    Jan 21 at 18:04














7












7








7





$begingroup$

Suppose it is simple and without loops.



If that one exist then if we delete node with degree $9$ and it edges, we would get a graph:



$$7,7,7,5,4,3,3,1,1$$



now if we delete node of degree $7$ and it edges we get



$$6,6,4,3,2,2,1,0;;;;{rm or} ;;;;geq 6,?,?,?,?,?,0,0$$



Second situation is impossible since at least one node of degree $0$ must be connected with first one with degree at least 6.



So suppose 1. situation is possible, then it is also: $$5,3,2,1,1,0$$



but this is actualy impossible (since at least one node of degree $0$ must be connected with first one with degree at least 5).



So such a graph does not exist.






share|cite|improve this answer











$endgroup$



Suppose it is simple and without loops.



If that one exist then if we delete node with degree $9$ and it edges, we would get a graph:



$$7,7,7,5,4,3,3,1,1$$



now if we delete node of degree $7$ and it edges we get



$$6,6,4,3,2,2,1,0;;;;{rm or} ;;;;geq 6,?,?,?,?,?,0,0$$



Second situation is impossible since at least one node of degree $0$ must be connected with first one with degree at least 6.



So suppose 1. situation is possible, then it is also: $$5,3,2,1,1,0$$



but this is actualy impossible (since at least one node of degree $0$ must be connected with first one with degree at least 5).



So such a graph does not exist.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited Jan 21 at 21:01

























answered Jan 21 at 17:28









greedoidgreedoid

39.7k114798




39.7k114798












  • $begingroup$
    Perfect thank you very much.
    $endgroup$
    – NotAbelianGroup
    Jan 21 at 18:04


















  • $begingroup$
    Perfect thank you very much.
    $endgroup$
    – NotAbelianGroup
    Jan 21 at 18:04
















$begingroup$
Perfect thank you very much.
$endgroup$
– NotAbelianGroup
Jan 21 at 18:04




$begingroup$
Perfect thank you very much.
$endgroup$
– NotAbelianGroup
Jan 21 at 18:04











5












$begingroup$

The answer is FALSE.



We proceed with the Havel–Hakimi Theorem, which determines whether a degree sequence can represent a simple graph.



Applying this theorem, we note that the original degree sequence is graphical if and only if the degree sequence given by ${7, 7, 7, 5, 4, 3, 3, 2, 1}$ is graphical. We can keep on reiterating to get the following degree lists:



$${6, 6, 4, 3, 2, 2, 1, 0} rightarrow {5, 3, 2, 1, 1, 0, 0} rightarrow {2, 1, 0, 0, 0, -1}$$



But, the last degree list is clearly not graphical: it has an edge with a negative degree! So, the answer is false.






share|cite|improve this answer











$endgroup$









  • 2




    $begingroup$
    Well, the given answer by the OP is "false" and thereby not false, :)
    $endgroup$
    – Hagen von Eitzen
    Jan 21 at 19:32






  • 1




    $begingroup$
    Are you sure you've applied the algorithm correctly (drop highest number $k$, subtract 1 from the next $k$ numbers, re-sort)? I get ${6,6,4,3,2,2,1,0}, {5,3,2,1,1,0,0}, {2,1,0,0,0,-1}$.
    $endgroup$
    – Paul Sinclair
    Jan 21 at 20:48












  • $begingroup$
    Oops, you are right. I just edited my post @PaulSinclair
    $endgroup$
    – Ekesh Kumar
    Jan 21 at 21:28
















5












$begingroup$

The answer is FALSE.



We proceed with the Havel–Hakimi Theorem, which determines whether a degree sequence can represent a simple graph.



Applying this theorem, we note that the original degree sequence is graphical if and only if the degree sequence given by ${7, 7, 7, 5, 4, 3, 3, 2, 1}$ is graphical. We can keep on reiterating to get the following degree lists:



$${6, 6, 4, 3, 2, 2, 1, 0} rightarrow {5, 3, 2, 1, 1, 0, 0} rightarrow {2, 1, 0, 0, 0, -1}$$



But, the last degree list is clearly not graphical: it has an edge with a negative degree! So, the answer is false.






share|cite|improve this answer











$endgroup$









  • 2




    $begingroup$
    Well, the given answer by the OP is "false" and thereby not false, :)
    $endgroup$
    – Hagen von Eitzen
    Jan 21 at 19:32






  • 1




    $begingroup$
    Are you sure you've applied the algorithm correctly (drop highest number $k$, subtract 1 from the next $k$ numbers, re-sort)? I get ${6,6,4,3,2,2,1,0}, {5,3,2,1,1,0,0}, {2,1,0,0,0,-1}$.
    $endgroup$
    – Paul Sinclair
    Jan 21 at 20:48












  • $begingroup$
    Oops, you are right. I just edited my post @PaulSinclair
    $endgroup$
    – Ekesh Kumar
    Jan 21 at 21:28














5












5








5





$begingroup$

The answer is FALSE.



We proceed with the Havel–Hakimi Theorem, which determines whether a degree sequence can represent a simple graph.



Applying this theorem, we note that the original degree sequence is graphical if and only if the degree sequence given by ${7, 7, 7, 5, 4, 3, 3, 2, 1}$ is graphical. We can keep on reiterating to get the following degree lists:



$${6, 6, 4, 3, 2, 2, 1, 0} rightarrow {5, 3, 2, 1, 1, 0, 0} rightarrow {2, 1, 0, 0, 0, -1}$$



But, the last degree list is clearly not graphical: it has an edge with a negative degree! So, the answer is false.






share|cite|improve this answer











$endgroup$



The answer is FALSE.



We proceed with the Havel–Hakimi Theorem, which determines whether a degree sequence can represent a simple graph.



Applying this theorem, we note that the original degree sequence is graphical if and only if the degree sequence given by ${7, 7, 7, 5, 4, 3, 3, 2, 1}$ is graphical. We can keep on reiterating to get the following degree lists:



$${6, 6, 4, 3, 2, 2, 1, 0} rightarrow {5, 3, 2, 1, 1, 0, 0} rightarrow {2, 1, 0, 0, 0, -1}$$



But, the last degree list is clearly not graphical: it has an edge with a negative degree! So, the answer is false.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited Jan 21 at 21:27

























answered Jan 21 at 17:49









Ekesh KumarEkesh Kumar

6146




6146








  • 2




    $begingroup$
    Well, the given answer by the OP is "false" and thereby not false, :)
    $endgroup$
    – Hagen von Eitzen
    Jan 21 at 19:32






  • 1




    $begingroup$
    Are you sure you've applied the algorithm correctly (drop highest number $k$, subtract 1 from the next $k$ numbers, re-sort)? I get ${6,6,4,3,2,2,1,0}, {5,3,2,1,1,0,0}, {2,1,0,0,0,-1}$.
    $endgroup$
    – Paul Sinclair
    Jan 21 at 20:48












  • $begingroup$
    Oops, you are right. I just edited my post @PaulSinclair
    $endgroup$
    – Ekesh Kumar
    Jan 21 at 21:28














  • 2




    $begingroup$
    Well, the given answer by the OP is "false" and thereby not false, :)
    $endgroup$
    – Hagen von Eitzen
    Jan 21 at 19:32






  • 1




    $begingroup$
    Are you sure you've applied the algorithm correctly (drop highest number $k$, subtract 1 from the next $k$ numbers, re-sort)? I get ${6,6,4,3,2,2,1,0}, {5,3,2,1,1,0,0}, {2,1,0,0,0,-1}$.
    $endgroup$
    – Paul Sinclair
    Jan 21 at 20:48












  • $begingroup$
    Oops, you are right. I just edited my post @PaulSinclair
    $endgroup$
    – Ekesh Kumar
    Jan 21 at 21:28








2




2




$begingroup$
Well, the given answer by the OP is "false" and thereby not false, :)
$endgroup$
– Hagen von Eitzen
Jan 21 at 19:32




$begingroup$
Well, the given answer by the OP is "false" and thereby not false, :)
$endgroup$
– Hagen von Eitzen
Jan 21 at 19:32




1




1




$begingroup$
Are you sure you've applied the algorithm correctly (drop highest number $k$, subtract 1 from the next $k$ numbers, re-sort)? I get ${6,6,4,3,2,2,1,0}, {5,3,2,1,1,0,0}, {2,1,0,0,0,-1}$.
$endgroup$
– Paul Sinclair
Jan 21 at 20:48






$begingroup$
Are you sure you've applied the algorithm correctly (drop highest number $k$, subtract 1 from the next $k$ numbers, re-sort)? I get ${6,6,4,3,2,2,1,0}, {5,3,2,1,1,0,0}, {2,1,0,0,0,-1}$.
$endgroup$
– Paul Sinclair
Jan 21 at 20:48














$begingroup$
Oops, you are right. I just edited my post @PaulSinclair
$endgroup$
– Ekesh Kumar
Jan 21 at 21:28




$begingroup$
Oops, you are right. I just edited my post @PaulSinclair
$endgroup$
– Ekesh Kumar
Jan 21 at 21:28


















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%2f3082125%2fdetermine-if-a-graph-exists-knowing-the-degree-of-its-vertices%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

An IMO inspired problem

Management

Has there ever been an instance of an active nuclear power plant within or near a war zone?