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

"Incorrect syntax near the keyword 'ON'. (on update cascade, on delete cascade,)

Image
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ height:90px;width:728px;box-sizing:border-box; } 2 total noob sorry any help greatly appreciated. I keep getting this "Incorrect syntax near the keyword 'ON'." heres my codes code one CREATE TABLE supplier ( supplierID INT PRIMARY KEY, ISBN INT FOREIGN KEY REFERENCES book(ISBN), price DECIMAL (5,2), ON UPDATE CASCADE, ON DELETE CASCADE, ); code two CREATE TABLE orders ( orderID INT PRIMARY KEY, customerID INT FOREIGN KEY REFERENCES customer(customerID), ISBN INT FOREIGN KEY REFERENCES book(ISBN), orderDate date, ON UPDATE CASCADE, ON DELETE CASCADE, ); Ive run out of stuff to try other than dumbing it down to uselessness.
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

Origin of the phrase “under your belt”?

Image
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ margin-bottom:0; } 17 1 Today, I found myself discussing what students should have "under their belts" during a lecture, and I wondered to myself if there was some inappropriate undertone here that I might be unaware of. Question : What is the origin of the phrase "under your belt"? A google search revealed some webpages (e.g. [1]) that assert its origin is related to consumption of food -- once a meal has been eaten, it's under your belt (which is a relief). However, with such websites, I have no way to determine fact from "random guy on the internet making stuff up". etymology idioms
Read more