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






combinatorics discrete-mathematics graph-theory







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?






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

1300-talet

Image
Den här artikeln handlar om hundraårsperioden 1300–1399. För decenniet 1300–1309, se 1300-talet (decennium). .mw-parser-output .infobox{border:1px solid #aaa;background-color:#f9f9f9;color:black;margin:.5em 0 .5em 1em;padding:.2em;float:right;clear:right;width:22em;text-align:left;font-size:88%;line-height:1.6em}.mw-parser-output .infobox td,.mw-parser-output .infobox th{vertical-align:top;padding:0 .2em}.mw-parser-output .infobox caption{font-size:larger}.mw-parser-output .infobox.bordered{border-collapse:collapse}.mw-parser-output .infobox.bordered td,.mw-parser-output .infobox.bordered th{border:1px solid #aaa}.mw-parser-output .infobox.bordered .borderless td,.mw-parser-output .infobox.bordered .borderless th{border:0}.mw-parser-output .infobox-showbutton .mw-collapsible-text{color:inherit}.mw-parser-output .infobox.bordered .mergedtoprow td,.mw-parser-output .infobox.bordered .mergedtoprow th{border:0;border-top:1px solid #aaa;border-right:1px solid #aaa}.mw-parser-output ...
Read more

1300-talet

Image
Den här artikeln handlar om hundraårsperioden 1300–1399. För decenniet 1300–1309, se 1300-talet (decennium). .mw-parser-output .infobox{border:1px solid #aaa;background-color:#f9f9f9;color:black;margin:.5em 0 .5em 1em;padding:.2em;float:right;clear:right;width:22em;text-align:left;font-size:88%;line-height:1.6em}.mw-parser-output .infobox td,.mw-parser-output .infobox th{vertical-align:top;padding:0 .2em}.mw-parser-output .infobox caption{font-size:larger}.mw-parser-output .infobox.bordered{border-collapse:collapse}.mw-parser-output .infobox.bordered td,.mw-parser-output .infobox.bordered th{border:1px solid #aaa}.mw-parser-output .infobox.bordered .borderless td,.mw-parser-output .infobox.bordered .borderless th{border:0}.mw-parser-output .infobox-showbutton .mw-collapsible-text{color:inherit}.mw-parser-output .infobox.bordered .mergedtoprow td,.mw-parser-output .infobox.bordered .mergedtoprow th{border:0;border-top:1px solid #aaa;border-right:1px solid #aaa}.mw-parser-output ...
Read more

Display a custom attribute below product name in the front-end Magento 1.9.3.8

Image
0 I need to display a custom attribute bellow the product name and I don't know how can I call this attribute. I am editing the file /app/design/frontend/templatemela/MAG100219_1/template/catalog/product/view.phtml But how can I call this attribute in php? I tried calling a string echo with the name I put in the attribute, but it didn't work. Code is as below: <div class="page-title product-title"> <h1><?php echo $_helper->productAttribute($_product, $_product->getName(), 'name') ?></h1> </div> <div class="codigoinmetro"> <h2><?php echo $_helper->productAttribute($_product, $_product->getName(), 'registroinmetro') ?></h2> </div> php attrib...
Read more