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?






combinatorics discrete-mathematics graph-theory







share|cite|improve this question











$endgroup$








  • 1




    $begingroup$
    Is that a simple graph?
    $endgroup$
    – greedoid
    2 days ago






  • 1




    $begingroup$
    @greedoid The professor didn't precise but since we only studied simple graph this semester I assume it is.
    $endgroup$
    – NotAbelianGroup
    2 days ago
















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?






combinatorics discrete-mathematics graph-theory







share|cite|improve this question











$endgroup$








  • 1




    $begingroup$
    Is that a simple graph?
    $endgroup$
    – greedoid
    2 days ago






  • 1




    $begingroup$
    @greedoid The professor didn't precise but since we only studied simple graph this semester I assume it is.
    $endgroup$
    – NotAbelianGroup
    2 days ago














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?






combinatorics discrete-mathematics graph-theory







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




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 2 days ago









greedoid

39.3k114797




39.3k114797










asked 2 days ago









NotAbelianGroupNotAbelianGroup

15511




15511








  • 1




    $begingroup$
    Is that a simple graph?
    $endgroup$
    – greedoid
    2 days ago






  • 1




    $begingroup$
    @greedoid The professor didn't precise but since we only studied simple graph this semester I assume it is.
    $endgroup$
    – NotAbelianGroup
    2 days ago














  • 1




    $begingroup$
    Is that a simple graph?
    $endgroup$
    – greedoid
    2 days ago






  • 1




    $begingroup$
    @greedoid The professor didn't precise but since we only studied simple graph this semester I assume it is.
    $endgroup$
    – NotAbelianGroup
    2 days ago








1




1




$begingroup$
Is that a simple graph?
$endgroup$
– greedoid
2 days ago




$begingroup$
Is that a simple graph?
$endgroup$
– greedoid
2 days ago




1




1




$begingroup$
@greedoid The professor didn't precise but since we only studied simple graph this semester I assume it is.
$endgroup$
– NotAbelianGroup
2 days ago




$begingroup$
@greedoid The professor didn't precise but since we only studied simple graph this semester I assume it is.
$endgroup$
– NotAbelianGroup
2 days ago










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
    2 days ago



















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
    2 days ago






  • 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
    2 days ago












  • $begingroup$
    Oops, you are right. I just edited my post @PaulSinclair
    $endgroup$
    – Ekesh Kumar
    2 days ago











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
    2 days ago
















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
    2 days ago














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 2 days ago

























answered 2 days ago









greedoidgreedoid

39.3k114797




39.3k114797












  • $begingroup$
    Perfect thank you very much.
    $endgroup$
    – NotAbelianGroup
    2 days ago


















  • $begingroup$
    Perfect thank you very much.
    $endgroup$
    – NotAbelianGroup
    2 days ago
















$begingroup$
Perfect thank you very much.
$endgroup$
– NotAbelianGroup
2 days ago




$begingroup$
Perfect thank you very much.
$endgroup$
– NotAbelianGroup
2 days ago











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
    2 days ago






  • 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
    2 days ago












  • $begingroup$
    Oops, you are right. I just edited my post @PaulSinclair
    $endgroup$
    – Ekesh Kumar
    2 days ago
















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
    2 days ago






  • 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
    2 days ago












  • $begingroup$
    Oops, you are right. I just edited my post @PaulSinclair
    $endgroup$
    – Ekesh Kumar
    2 days ago














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 2 days ago

























answered 2 days ago









Ekesh KumarEkesh Kumar

6146




6146








  • 2




    $begingroup$
    Well, the given answer by the OP is "false" and thereby not false, :)
    $endgroup$
    – Hagen von Eitzen
    2 days ago






  • 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
    2 days ago












  • $begingroup$
    Oops, you are right. I just edited my post @PaulSinclair
    $endgroup$
    – Ekesh Kumar
    2 days ago














  • 2




    $begingroup$
    Well, the given answer by the OP is "false" and thereby not false, :)
    $endgroup$
    – Hagen von Eitzen
    2 days ago






  • 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
    2 days ago












  • $begingroup$
    Oops, you are right. I just edited my post @PaulSinclair
    $endgroup$
    – Ekesh Kumar
    2 days ago








2




2




$begingroup$
Well, the given answer by the OP is "false" and thereby not false, :)
$endgroup$
– Hagen von Eitzen
2 days ago




$begingroup$
Well, the given answer by the OP is "false" and thereby not false, :)
$endgroup$
– Hagen von Eitzen
2 days ago




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
2 days ago






$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
2 days ago














$begingroup$
Oops, you are right. I just edited my post @PaulSinclair
$endgroup$
– Ekesh Kumar
2 days ago




$begingroup$
Oops, you are right. I just edited my post @PaulSinclair
$endgroup$
– Ekesh Kumar
2 days ago


















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

If I really need a card on my start hand, how many mulligans make sense? [duplicate]

Image
5 This question already has an answer here: How do you calculate the likelihood of drawing certain cards in your opening hand? 3 answers There is a funny modern deck where you play Treasure Hunt, but you really need to have it on the starting hand. How many mulligans should I take, if my deck contains 60 cards and contains 4 copies of Treasure Hunt? magic-the-gathering probability share | improve this question asked Nov 23 '18 at 12:12 dan dan 152 4
Read more

Alcedinidae

Image
Alcedinidae Martin-pêcheur à dos bleu ( Alcedo azurea ) Classification (COI) Règne Animalia Embranchement Chordata Sous-embr. Vertebrata Classe Aves Ordre Coraciiformes Famille Alcedinidae Rafinesque, 1815 Les Alcédinidés ou Alcedinidae forment une famille d'oiseaux plus connus sous les noms de martins-pêcheurs et martins-chasseurs. Sommaire 1 Description 2 Répartition et habitat 3 Systématique 3.1 Liste alphabétique des genres 3.2 Liste des espèces 4 Chez les Anciens : l'alcyon 4.1 Étymologie (Littré) 4.2 Oiseau « fabuleux » ? 5 Notes 6 Articles connexes 7 Liens externes 7.1 Bibliographie Description | Ce sont des oiseaux compacts de taille petite à moyenne (10 à 46 cm), au bec droit et long, en forme de poignard. Leurs pattes sont courtes, et ils portent un plumage aux couleurs vives. Répartition et habitat | Cosmopolites, ils fréquentent surtout
Read more

Can an atomic nucleus contain both particles and antiparticles? [duplicate]

Image
9 $begingroup$ This question already has an answer here: What happens if we put together a proton and an antineutron? 2 answers Is it theoretically possible to make a "deuterium" atom containing a proton and an antineutron in its nucleus? Would the strong nuclear force cause attraction between a proton and an antineutron? Would such a nucleus be stable, or would the proton somehow annihilate the antineutron when close enough? nuclear-physics antimatter share | cite | improve this question asked yesterday
Read more