Vertex and graph
$begingroup$
Question : A graph has 11 vertices classified as follows: six vertices have degree 3, one vertex has degree 4, two have degree 5 and two have degree 6. How many edges does this graph have?
I started to draw the graph but I could not fit with the requirements. I draw first the vertex with largest degrees (6, after 5 etc) but at the end it does not work.
What is the easiest way to approach this problem?
discrete-mathematics graph-theory
asked Dec 8 '18 at 20:40
Tom1999Tom1999
445
$endgroup$
add a comment |
$begingroup$
Question : A graph has 11 vertices classified as follows: six vertices have degree 3, one vertex has degree 4, two have degree 5 and two have degree 6. How many edges does this graph have?
I started to draw the graph but I could not fit with the requirements. I draw first the vertex with largest degrees (6, after 5 etc) but at the end it does not work.
What is the easiest way to approach this problem?
discrete-mathematics graph-theory
asked Dec 8 '18 at 20:40
Tom1999Tom1999
445
$endgroup$
add a comment |
$begingroup$
Question : A graph has 11 vertices classified as follows: six vertices have degree 3, one vertex has degree 4, two have degree 5 and two have degree 6. How many edges does this graph have?
I started to draw the graph but I could not fit with the requirements. I draw first the vertex with largest degrees (6, after 5 etc) but at the end it does not work.
What is the easiest way to approach this problem?
discrete-mathematics graph-theory
asked Dec 8 '18 at 20:40
Tom1999Tom1999
445
$endgroup$
Question : A graph has 11 vertices classified as follows: six vertices have degree 3, one vertex has degree 4, two have degree 5 and two have degree 6. How many edges does this graph have?
I started to draw the graph but I could not fit with the requirements. I draw first the vertex with largest degrees (6, after 5 etc) but at the end it does not work.
What is the easiest way to approach this problem?
discrete-mathematics graph-theory
discrete-mathematics graph-theory
asked Dec 8 '18 at 20:40
Tom1999Tom1999
445
asked Dec 8 '18 at 20:40
Tom1999Tom1999
445
asked Dec 8 '18 at 20:40
Tom1999Tom1999
445
asked Dec 8 '18 at 20:40
Tom1999Tom1999
445
asked Dec 8 '18 at 20:40
Tom1999Tom1999
445
445
add a comment |
add a comment |
4 Answers
4
active
oldest
votes
$begingroup$
Number of edges multiplied by $2$ equals to the total sum of degrees.
(Think about it, easy double counting argument.)
Of course, it is important that the conditions be consistent, so you do need to prove that such a graph exists. (I.e., it was a good idea to try to draw one.)
answered Dec 8 '18 at 20:46
A. PongráczA. Pongrácz
5,9731929
$endgroup$
add a comment |
$begingroup$
The following graph satisfy the requirment and it has 22 edges:
answered Dec 8 '18 at 21:32
nafhgoodnafhgood
1,803422
$endgroup$
1
$begingroup$
That appears to meet the requirements for the graph (and has the needed 22 edges), but the OP didn't ask for the graph, they asked the easiest way to approach the problem.
$endgroup$
– T. M.
Dec 8 '18 at 21:46
1
$begingroup$
(It has 22 edges.) But more importantly: @T. M. I disagree, this is an important part of the proof. If you use the standard formula I referred to in my answer, it gives you that the only possible number of edges for such a graph is $22$. If you do not show such a graph (or prove it exists somehow), then theoretically speaking, it is possible that no such graph exists, in which case the answer to the question is: ANYTHING AT ALL. (Even "Brad Pitt" is a correct answer then.) However, once you show such a graph, the answer is $22$. Huge difference.
$endgroup$
– A. Pongrácz
Dec 8 '18 at 22:36
1
$begingroup$
@A. Pongrácz I agree with the need for the graph, my point was posting it without any hint as to how to find it doesn't help the OP to solve any similar problems. Beyond confirming what you already said.
$endgroup$
– T. M.
Dec 9 '18 at 0:18
add a comment |
$begingroup$
Ok, this problem felt like it would have some good theory behind it and it does. The general problem, called the Graph realization problem, is given a degree sequence, does a simple graph exist with that degree sequence. That article discusses two known methods, the Havel–Hakimi algorithm, and the other is following the Erdős–Gallai theorem. There are a number of posts on SE about the Havel–Hakimi algorithm. If you follow HH, it also shows how to construct a graph with the given degree sequence.
answered Dec 10 '18 at 4:09
T. M.T. M.
245110
$endgroup$
add a comment |
$begingroup$
You can think all the vertices are seperate and has connectible branches as many as their degree's. Then start counting.
For example:
One of the six degree vertex will make six edges. Count'em as six edges and delete six other connectible branch from other nodes. After all you will left with one 4 degree vertex and it will make 2 edges. Total number of edges will be 22.enter image description here
answered Dec 12 '18 at 7:37
Ahmet Mert SayguAhmet Mert Saygu
1
$endgroup$
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
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3031615%2fvertex-and-graph%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Number of edges multiplied by $2$ equals to the total sum of degrees.
(Think about it, easy double counting argument.)
Of course, it is important that the conditions be consistent, so you do need to prove that such a graph exists. (I.e., it was a good idea to try to draw one.)
answered Dec 8 '18 at 20:46
A. PongráczA. Pongrácz
5,9731929
$endgroup$
add a comment |
$begingroup$
Number of edges multiplied by $2$ equals to the total sum of degrees.
(Think about it, easy double counting argument.)
Of course, it is important that the conditions be consistent, so you do need to prove that such a graph exists. (I.e., it was a good idea to try to draw one.)
answered Dec 8 '18 at 20:46
A. PongráczA. Pongrácz
5,9731929
$endgroup$
add a comment |
$begingroup$
Number of edges multiplied by $2$ equals to the total sum of degrees.
(Think about it, easy double counting argument.)
Of course, it is important that the conditions be consistent, so you do need to prove that such a graph exists. (I.e., it was a good idea to try to draw one.)
answered Dec 8 '18 at 20:46
A. PongráczA. Pongrácz
5,9731929
$endgroup$
Number of edges multiplied by $2$ equals to the total sum of degrees.
(Think about it, easy double counting argument.)
Of course, it is important that the conditions be consistent, so you do need to prove that such a graph exists. (I.e., it was a good idea to try to draw one.)
answered Dec 8 '18 at 20:46
A. PongráczA. Pongrácz
5,9731929
answered Dec 8 '18 at 20:46
A. PongráczA. Pongrácz
5,9731929
answered Dec 8 '18 at 20:46
A. PongráczA. Pongrácz
5,9731929
answered Dec 8 '18 at 20:46
A. PongráczA. Pongrácz
5,9731929
5,9731929
add a comment |
add a comment |
$begingroup$
The following graph satisfy the requirment and it has 22 edges:
answered Dec 8 '18 at 21:32
nafhgoodnafhgood
1,803422
$endgroup$
1
$begingroup$
That appears to meet the requirements for the graph (and has the needed 22 edges), but the OP didn't ask for the graph, they asked the easiest way to approach the problem.
$endgroup$
– T. M.
Dec 8 '18 at 21:46
1
$begingroup$
(It has 22 edges.) But more importantly: @T. M. I disagree, this is an important part of the proof. If you use the standard formula I referred to in my answer, it gives you that the only possible number of edges for such a graph is $22$. If you do not show such a graph (or prove it exists somehow), then theoretically speaking, it is possible that no such graph exists, in which case the answer to the question is: ANYTHING AT ALL. (Even "Brad Pitt" is a correct answer then.) However, once you show such a graph, the answer is $22$. Huge difference.
$endgroup$
– A. Pongrácz
Dec 8 '18 at 22:36
1
$begingroup$
@A. Pongrácz I agree with the need for the graph, my point was posting it without any hint as to how to find it doesn't help the OP to solve any similar problems. Beyond confirming what you already said.
$endgroup$
– T. M.
Dec 9 '18 at 0:18
add a comment |
$begingroup$
The following graph satisfy the requirment and it has 22 edges:
answered Dec 8 '18 at 21:32
nafhgoodnafhgood
1,803422
$endgroup$
1
$begingroup$
That appears to meet the requirements for the graph (and has the needed 22 edges), but the OP didn't ask for the graph, they asked the easiest way to approach the problem.
$endgroup$
– T. M.
Dec 8 '18 at 21:46
1
$begingroup$
(It has 22 edges.) But more importantly: @T. M. I disagree, this is an important part of the proof. If you use the standard formula I referred to in my answer, it gives you that the only possible number of edges for such a graph is $22$. If you do not show such a graph (or prove it exists somehow), then theoretically speaking, it is possible that no such graph exists, in which case the answer to the question is: ANYTHING AT ALL. (Even "Brad Pitt" is a correct answer then.) However, once you show such a graph, the answer is $22$. Huge difference.
$endgroup$
– A. Pongrácz
Dec 8 '18 at 22:36
1
$begingroup$
@A. Pongrácz I agree with the need for the graph, my point was posting it without any hint as to how to find it doesn't help the OP to solve any similar problems. Beyond confirming what you already said.
$endgroup$
– T. M.
Dec 9 '18 at 0:18
add a comment |
$begingroup$
The following graph satisfy the requirment and it has 22 edges:
answered Dec 8 '18 at 21:32
nafhgoodnafhgood
1,803422
$endgroup$
The following graph satisfy the requirment and it has 22 edges:
answered Dec 8 '18 at 21:32
nafhgoodnafhgood
1,803422
edited Dec 8 '18 at 22:37
answered Dec 8 '18 at 21:32
nafhgoodnafhgood
1,803422
answered Dec 8 '18 at 21:32
nafhgoodnafhgood
1,803422
answered Dec 8 '18 at 21:32
nafhgoodnafhgood
1,803422
1,803422
1
$begingroup$
That appears to meet the requirements for the graph (and has the needed 22 edges), but the OP didn't ask for the graph, they asked the easiest way to approach the problem.
$endgroup$
– T. M.
Dec 8 '18 at 21:46
1
$begingroup$
(It has 22 edges.) But more importantly: @T. M. I disagree, this is an important part of the proof. If you use the standard formula I referred to in my answer, it gives you that the only possible number of edges for such a graph is $22$. If you do not show such a graph (or prove it exists somehow), then theoretically speaking, it is possible that no such graph exists, in which case the answer to the question is: ANYTHING AT ALL. (Even "Brad Pitt" is a correct answer then.) However, once you show such a graph, the answer is $22$. Huge difference.
$endgroup$
– A. Pongrácz
Dec 8 '18 at 22:36
1
$begingroup$
@A. Pongrácz I agree with the need for the graph, my point was posting it without any hint as to how to find it doesn't help the OP to solve any similar problems. Beyond confirming what you already said.
$endgroup$
– T. M.
Dec 9 '18 at 0:18
add a comment |
1
$begingroup$
That appears to meet the requirements for the graph (and has the needed 22 edges), but the OP didn't ask for the graph, they asked the easiest way to approach the problem.
$endgroup$
– T. M.
Dec 8 '18 at 21:46
1
$begingroup$
(It has 22 edges.) But more importantly: @T. M. I disagree, this is an important part of the proof. If you use the standard formula I referred to in my answer, it gives you that the only possible number of edges for such a graph is $22$. If you do not show such a graph (or prove it exists somehow), then theoretically speaking, it is possible that no such graph exists, in which case the answer to the question is: ANYTHING AT ALL. (Even "Brad Pitt" is a correct answer then.) However, once you show such a graph, the answer is $22$. Huge difference.
$endgroup$
– A. Pongrácz
Dec 8 '18 at 22:36
1
$begingroup$
@A. Pongrácz I agree with the need for the graph, my point was posting it without any hint as to how to find it doesn't help the OP to solve any similar problems. Beyond confirming what you already said.
$endgroup$
– T. M.
Dec 9 '18 at 0:18
1
1
$begingroup$
That appears to meet the requirements for the graph (and has the needed 22 edges), but the OP didn't ask for the graph, they asked the easiest way to approach the problem.
$endgroup$
– T. M.
Dec 8 '18 at 21:46
$begingroup$
That appears to meet the requirements for the graph (and has the needed 22 edges), but the OP didn't ask for the graph, they asked the easiest way to approach the problem.
$endgroup$
– T. M.
Dec 8 '18 at 21:46
1
1
$begingroup$
(It has 22 edges.) But more importantly: @T. M. I disagree, this is an important part of the proof. If you use the standard formula I referred to in my answer, it gives you that the only possible number of edges for such a graph is $22$. If you do not show such a graph (or prove it exists somehow), then theoretically speaking, it is possible that no such graph exists, in which case the answer to the question is: ANYTHING AT ALL. (Even "Brad Pitt" is a correct answer then.) However, once you show such a graph, the answer is $22$. Huge difference.
$endgroup$
– A. Pongrácz
Dec 8 '18 at 22:36
$begingroup$
(It has 22 edges.) But more importantly: @T. M. I disagree, this is an important part of the proof. If you use the standard formula I referred to in my answer, it gives you that the only possible number of edges for such a graph is $22$. If you do not show such a graph (or prove it exists somehow), then theoretically speaking, it is possible that no such graph exists, in which case the answer to the question is: ANYTHING AT ALL. (Even "Brad Pitt" is a correct answer then.) However, once you show such a graph, the answer is $22$. Huge difference.
$endgroup$
– A. Pongrácz
Dec 8 '18 at 22:36
1
1
$begingroup$
@A. Pongrácz I agree with the need for the graph, my point was posting it without any hint as to how to find it doesn't help the OP to solve any similar problems. Beyond confirming what you already said.
$endgroup$
– T. M.
Dec 9 '18 at 0:18
$begingroup$
@A. Pongrácz I agree with the need for the graph, my point was posting it without any hint as to how to find it doesn't help the OP to solve any similar problems. Beyond confirming what you already said.
$endgroup$
– T. M.
Dec 9 '18 at 0:18
add a comment |
$begingroup$
Ok, this problem felt like it would have some good theory behind it and it does. The general problem, called the Graph realization problem, is given a degree sequence, does a simple graph exist with that degree sequence. That article discusses two known methods, the Havel–Hakimi algorithm, and the other is following the Erdős–Gallai theorem. There are a number of posts on SE about the Havel–Hakimi algorithm. If you follow HH, it also shows how to construct a graph with the given degree sequence.
answered Dec 10 '18 at 4:09
T. M.T. M.
245110
$endgroup$
add a comment |
$begingroup$
Ok, this problem felt like it would have some good theory behind it and it does. The general problem, called the Graph realization problem, is given a degree sequence, does a simple graph exist with that degree sequence. That article discusses two known methods, the Havel–Hakimi algorithm, and the other is following the Erdős–Gallai theorem. There are a number of posts on SE about the Havel–Hakimi algorithm. If you follow HH, it also shows how to construct a graph with the given degree sequence.
answered Dec 10 '18 at 4:09
T. M.T. M.
245110
$endgroup$
add a comment |
$begingroup$
Ok, this problem felt like it would have some good theory behind it and it does. The general problem, called the Graph realization problem, is given a degree sequence, does a simple graph exist with that degree sequence. That article discusses two known methods, the Havel–Hakimi algorithm, and the other is following the Erdős–Gallai theorem. There are a number of posts on SE about the Havel–Hakimi algorithm. If you follow HH, it also shows how to construct a graph with the given degree sequence.
answered Dec 10 '18 at 4:09
T. M.T. M.
245110
$endgroup$
Ok, this problem felt like it would have some good theory behind it and it does. The general problem, called the Graph realization problem, is given a degree sequence, does a simple graph exist with that degree sequence. That article discusses two known methods, the Havel–Hakimi algorithm, and the other is following the Erdős–Gallai theorem. There are a number of posts on SE about the Havel–Hakimi algorithm. If you follow HH, it also shows how to construct a graph with the given degree sequence.
answered Dec 10 '18 at 4:09
T. M.T. M.
245110
answered Dec 10 '18 at 4:09
T. M.T. M.
245110
answered Dec 10 '18 at 4:09
T. M.T. M.
245110
answered Dec 10 '18 at 4:09
T. M.T. M.
245110
245110
add a comment |
add a comment |
$begingroup$
You can think all the vertices are seperate and has connectible branches as many as their degree's. Then start counting.
For example:
One of the six degree vertex will make six edges. Count'em as six edges and delete six other connectible branch from other nodes. After all you will left with one 4 degree vertex and it will make 2 edges. Total number of edges will be 22.enter image description here
answered Dec 12 '18 at 7:37
Ahmet Mert SayguAhmet Mert Saygu
1
$endgroup$
add a comment |
$begingroup$
You can think all the vertices are seperate and has connectible branches as many as their degree's. Then start counting.
For example:
One of the six degree vertex will make six edges. Count'em as six edges and delete six other connectible branch from other nodes. After all you will left with one 4 degree vertex and it will make 2 edges. Total number of edges will be 22.enter image description here
answered Dec 12 '18 at 7:37
Ahmet Mert SayguAhmet Mert Saygu
1
$endgroup$
add a comment |
$begingroup$
You can think all the vertices are seperate and has connectible branches as many as their degree's. Then start counting.
For example:
One of the six degree vertex will make six edges. Count'em as six edges and delete six other connectible branch from other nodes. After all you will left with one 4 degree vertex and it will make 2 edges. Total number of edges will be 22.enter image description here
answered Dec 12 '18 at 7:37
Ahmet Mert SayguAhmet Mert Saygu
1
$endgroup$
You can think all the vertices are seperate and has connectible branches as many as their degree's. Then start counting.
For example:
One of the six degree vertex will make six edges. Count'em as six edges and delete six other connectible branch from other nodes. After all you will left with one 4 degree vertex and it will make 2 edges. Total number of edges will be 22.enter image description here
answered Dec 12 '18 at 7:37
Ahmet Mert SayguAhmet Mert Saygu
1
answered Dec 12 '18 at 7:37
Ahmet Mert SayguAhmet Mert Saygu
1
answered Dec 12 '18 at 7:37
Ahmet Mert SayguAhmet Mert Saygu
1
answered Dec 12 '18 at 7:37
Ahmet Mert SayguAhmet Mert Saygu
1
1
add a comment |
add a comment |
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.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3031615%2fvertex-and-graph%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
