Draw a planar graph with two vertices of degree 3 and four vertices of degree 5, if possible.
Draw a planar graph with two vertices of degree 3 and four vertices of degree 5, if possible.
Attempt:
With handshaking lemma, I get this:
$2e = 26 implies e=13$
Then with Euler's formula, I get:
$6-13+f=2 implies f = 9$
However, since $e leq 3v - 6$ for a simple, connected, planar graph I would get:
$13 leq 3(6)-6$
$13 leq 12$
I can't figure out how I could get 9 faces for my graph. I can only get 8 faces as shown here:
This is the best attempt I had on this problem with no success.
combinatorics graph-theory
edited Dec 9 at 9:32
greedoid
37.7k114794
asked Dec 9 at 0:36
cosmicbrownie
1016
add a comment |
Draw a planar graph with two vertices of degree 3 and four vertices of degree 5, if possible.
Attempt:
With handshaking lemma, I get this:
$2e = 26 implies e=13$
Then with Euler's formula, I get:
$6-13+f=2 implies f = 9$
However, since $e leq 3v - 6$ for a simple, connected, planar graph I would get:
$13 leq 3(6)-6$
$13 leq 12$
I can't figure out how I could get 9 faces for my graph. I can only get 8 faces as shown here:
This is the best attempt I had on this problem with no success.
combinatorics graph-theory
edited Dec 9 at 9:32
greedoid
37.7k114794
asked Dec 9 at 0:36
cosmicbrownie
1016
Euler's formula counts the external face. Your graph has 9.
– Misha Lavrov
Dec 9 at 2:50
3 minutes. $ $ $ $
– Did
Dec 9 at 10:54
I had no trouble drawing a simple connected planar graph with two vertices of degree $3$ and four vertices of degree $5$. It is a tree of order $22$. (Was there some other condition you didn't mention?)
– bof
Dec 9 at 10:59
add a comment |
Draw a planar graph with two vertices of degree 3 and four vertices of degree 5, if possible.
Attempt:
With handshaking lemma, I get this:
$2e = 26 implies e=13$
Then with Euler's formula, I get:
$6-13+f=2 implies f = 9$
However, since $e leq 3v - 6$ for a simple, connected, planar graph I would get:
$13 leq 3(6)-6$
$13 leq 12$
I can't figure out how I could get 9 faces for my graph. I can only get 8 faces as shown here:
This is the best attempt I had on this problem with no success.
combinatorics graph-theory
edited Dec 9 at 9:32
greedoid
37.7k114794
asked Dec 9 at 0:36
cosmicbrownie
1016
Draw a planar graph with two vertices of degree 3 and four vertices of degree 5, if possible.
Attempt:
With handshaking lemma, I get this:
$2e = 26 implies e=13$
Then with Euler's formula, I get:
$6-13+f=2 implies f = 9$
However, since $e leq 3v - 6$ for a simple, connected, planar graph I would get:
$13 leq 3(6)-6$
$13 leq 12$
I can't figure out how I could get 9 faces for my graph. I can only get 8 faces as shown here:
This is the best attempt I had on this problem with no success.
combinatorics graph-theory
combinatorics graph-theory
edited Dec 9 at 9:32
greedoid
37.7k114794
asked Dec 9 at 0:36
cosmicbrownie
1016
edited Dec 9 at 9:32
greedoid
37.7k114794
asked Dec 9 at 0:36
cosmicbrownie
1016
edited Dec 9 at 9:32
greedoid
37.7k114794
edited Dec 9 at 9:32
greedoid
37.7k114794
edited Dec 9 at 9:32
greedoid
37.7k114794
37.7k114794
asked Dec 9 at 0:36
cosmicbrownie
1016
asked Dec 9 at 0:36
cosmicbrownie
1016
asked Dec 9 at 0:36
cosmicbrownie
1016
1016
Euler's formula counts the external face. Your graph has 9.
– Misha Lavrov
Dec 9 at 2:50
3 minutes. $ $ $ $
– Did
Dec 9 at 10:54
I had no trouble drawing a simple connected planar graph with two vertices of degree $3$ and four vertices of degree $5$. It is a tree of order $22$. (Was there some other condition you didn't mention?)
– bof
Dec 9 at 10:59
add a comment |
Euler's formula counts the external face. Your graph has 9.
– Misha Lavrov
Dec 9 at 2:50
3 minutes. $ $ $ $
– Did
Dec 9 at 10:54
I had no trouble drawing a simple connected planar graph with two vertices of degree $3$ and four vertices of degree $5$. It is a tree of order $22$. (Was there some other condition you didn't mention?)
– bof
Dec 9 at 10:59
Euler's formula counts the external face. Your graph has 9.
– Misha Lavrov
Dec 9 at 2:50
Euler's formula counts the external face. Your graph has 9.
– Misha Lavrov
Dec 9 at 2:50
3 minutes. $ $ $ $
– Did
Dec 9 at 10:54
3 minutes. $ $ $ $
– Did
Dec 9 at 10:54
I had no trouble drawing a simple connected planar graph with two vertices of degree $3$ and four vertices of degree $5$. It is a tree of order $22$. (Was there some other condition you didn't mention?)
– bof
Dec 9 at 10:59
I had no trouble drawing a simple connected planar graph with two vertices of degree $3$ and four vertices of degree $5$. It is a tree of order $22$. (Was there some other condition you didn't mention?)
– bof
Dec 9 at 10:59
add a comment |
2 Answers
2
active
oldest
votes
Here is a planar example. The vertices A and B are linked by two simple edges. The vertices A, B, E and F have degree 5. The vertices C and D have degree 3.
answered Dec 9 at 10:35
Did
246k23220454
1
@greedoid 5. As is mentioned in my post.
– Did
Dec 9 at 11:03
I don't understand. What have I proved then?
– greedoid
Dec 9 at 11:05
@greedoid That no graph such that, between two given vertices, there are either zero or one edge, solves the question. And I provided a graph solving the question such that, between two given vertices, there are either zero or one or two edges (when one admits more than one edge, these are often called multi-edged graphs). No mathematical mystery here. (But the reason why the OP, who is obviously considering graphs with multi-edges, chose to instantly accept an answer dealing only with graphs without multi-edge, is a true mystery, yes.)
– Did
Dec 9 at 11:15
add a comment |
From formula you wrote $eleq 3v-6$ you can see that such a (planar) graph does not exist.
Also you could note that this graph contains $K_{3,3}$ so again it can not be planar.
Edit: Actualy this graph doesn't even exist since the sequence $5,5,5,5,3,3$ is not graphicaly. If it is, then following would be also
$$ 4,4,4,2,2implies 3,3,1,1implies 2,0,0$$
but last one clearly it is not graphicaly.
answered Dec 9 at 0:44
greedoid
37.7k114794
Can you still get a planar graph even if it's not a simple, connected one based on the formula? I thought that formula was just for simple, connected planar graphs.
– cosmicbrownie
Dec 9 at 0:47
Yes it is, but your graph is clearly connected, it has to many edges to not be connected
– greedoid
Dec 9 at 0:48
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%2f3031861%2fdraw-a-planar-graph-with-two-vertices-of-degree-3-and-four-vertices-of-degree-5%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
Here is a planar example. The vertices A and B are linked by two simple edges. The vertices A, B, E and F have degree 5. The vertices C and D have degree 3.
answered Dec 9 at 10:35
Did
246k23220454
1
@greedoid 5. As is mentioned in my post.
– Did
Dec 9 at 11:03
I don't understand. What have I proved then?
– greedoid
Dec 9 at 11:05
@greedoid That no graph such that, between two given vertices, there are either zero or one edge, solves the question. And I provided a graph solving the question such that, between two given vertices, there are either zero or one or two edges (when one admits more than one edge, these are often called multi-edged graphs). No mathematical mystery here. (But the reason why the OP, who is obviously considering graphs with multi-edges, chose to instantly accept an answer dealing only with graphs without multi-edge, is a true mystery, yes.)
– Did
Dec 9 at 11:15
add a comment |
Here is a planar example. The vertices A and B are linked by two simple edges. The vertices A, B, E and F have degree 5. The vertices C and D have degree 3.
answered Dec 9 at 10:35
Did
246k23220454
1
@greedoid 5. As is mentioned in my post.
– Did
Dec 9 at 11:03
I don't understand. What have I proved then?
– greedoid
Dec 9 at 11:05
@greedoid That no graph such that, between two given vertices, there are either zero or one edge, solves the question. And I provided a graph solving the question such that, between two given vertices, there are either zero or one or two edges (when one admits more than one edge, these are often called multi-edged graphs). No mathematical mystery here. (But the reason why the OP, who is obviously considering graphs with multi-edges, chose to instantly accept an answer dealing only with graphs without multi-edge, is a true mystery, yes.)
– Did
Dec 9 at 11:15
add a comment |
Here is a planar example. The vertices A and B are linked by two simple edges. The vertices A, B, E and F have degree 5. The vertices C and D have degree 3.
answered Dec 9 at 10:35
Did
246k23220454
Here is a planar example. The vertices A and B are linked by two simple edges. The vertices A, B, E and F have degree 5. The vertices C and D have degree 3.
answered Dec 9 at 10:35
Did
246k23220454
edited Dec 9 at 10:57
answered Dec 9 at 10:35
Did
246k23220454
answered Dec 9 at 10:35
Did
246k23220454
answered Dec 9 at 10:35
Did
246k23220454
246k23220454
1
@greedoid 5. As is mentioned in my post.
– Did
Dec 9 at 11:03
I don't understand. What have I proved then?
– greedoid
Dec 9 at 11:05
@greedoid That no graph such that, between two given vertices, there are either zero or one edge, solves the question. And I provided a graph solving the question such that, between two given vertices, there are either zero or one or two edges (when one admits more than one edge, these are often called multi-edged graphs). No mathematical mystery here. (But the reason why the OP, who is obviously considering graphs with multi-edges, chose to instantly accept an answer dealing only with graphs without multi-edge, is a true mystery, yes.)
– Did
Dec 9 at 11:15
add a comment |
1
@greedoid 5. As is mentioned in my post.
– Did
Dec 9 at 11:03
I don't understand. What have I proved then?
– greedoid
Dec 9 at 11:05
@greedoid That no graph such that, between two given vertices, there are either zero or one edge, solves the question. And I provided a graph solving the question such that, between two given vertices, there are either zero or one or two edges (when one admits more than one edge, these are often called multi-edged graphs). No mathematical mystery here. (But the reason why the OP, who is obviously considering graphs with multi-edges, chose to instantly accept an answer dealing only with graphs without multi-edge, is a true mystery, yes.)
– Did
Dec 9 at 11:15
1
1
@greedoid 5. As is mentioned in my post.
– Did
Dec 9 at 11:03
@greedoid 5. As is mentioned in my post.
– Did
Dec 9 at 11:03
I don't understand. What have I proved then?
– greedoid
Dec 9 at 11:05
I don't understand. What have I proved then?
– greedoid
Dec 9 at 11:05
@greedoid That no graph such that, between two given vertices, there are either zero or one edge, solves the question. And I provided a graph solving the question such that, between two given vertices, there are either zero or one or two edges (when one admits more than one edge, these are often called multi-edged graphs). No mathematical mystery here. (But the reason why the OP, who is obviously considering graphs with multi-edges, chose to instantly accept an answer dealing only with graphs without multi-edge, is a true mystery, yes.)
– Did
Dec 9 at 11:15
@greedoid That no graph such that, between two given vertices, there are either zero or one edge, solves the question. And I provided a graph solving the question such that, between two given vertices, there are either zero or one or two edges (when one admits more than one edge, these are often called multi-edged graphs). No mathematical mystery here. (But the reason why the OP, who is obviously considering graphs with multi-edges, chose to instantly accept an answer dealing only with graphs without multi-edge, is a true mystery, yes.)
– Did
Dec 9 at 11:15
add a comment |
From formula you wrote $eleq 3v-6$ you can see that such a (planar) graph does not exist.
Also you could note that this graph contains $K_{3,3}$ so again it can not be planar.
Edit: Actualy this graph doesn't even exist since the sequence $5,5,5,5,3,3$ is not graphicaly. If it is, then following would be also
$$ 4,4,4,2,2implies 3,3,1,1implies 2,0,0$$
but last one clearly it is not graphicaly.
answered Dec 9 at 0:44
greedoid
37.7k114794
Can you still get a planar graph even if it's not a simple, connected one based on the formula? I thought that formula was just for simple, connected planar graphs.
– cosmicbrownie
Dec 9 at 0:47
Yes it is, but your graph is clearly connected, it has to many edges to not be connected
– greedoid
Dec 9 at 0:48
add a comment |
From formula you wrote $eleq 3v-6$ you can see that such a (planar) graph does not exist.
Also you could note that this graph contains $K_{3,3}$ so again it can not be planar.
Edit: Actualy this graph doesn't even exist since the sequence $5,5,5,5,3,3$ is not graphicaly. If it is, then following would be also
$$ 4,4,4,2,2implies 3,3,1,1implies 2,0,0$$
but last one clearly it is not graphicaly.
answered Dec 9 at 0:44
greedoid
37.7k114794
Can you still get a planar graph even if it's not a simple, connected one based on the formula? I thought that formula was just for simple, connected planar graphs.
– cosmicbrownie
Dec 9 at 0:47
Yes it is, but your graph is clearly connected, it has to many edges to not be connected
– greedoid
Dec 9 at 0:48
add a comment |
From formula you wrote $eleq 3v-6$ you can see that such a (planar) graph does not exist.
Also you could note that this graph contains $K_{3,3}$ so again it can not be planar.
Edit: Actualy this graph doesn't even exist since the sequence $5,5,5,5,3,3$ is not graphicaly. If it is, then following would be also
$$ 4,4,4,2,2implies 3,3,1,1implies 2,0,0$$
but last one clearly it is not graphicaly.
answered Dec 9 at 0:44
greedoid
37.7k114794
From formula you wrote $eleq 3v-6$ you can see that such a (planar) graph does not exist.
Also you could note that this graph contains $K_{3,3}$ so again it can not be planar.
Edit: Actualy this graph doesn't even exist since the sequence $5,5,5,5,3,3$ is not graphicaly. If it is, then following would be also
$$ 4,4,4,2,2implies 3,3,1,1implies 2,0,0$$
but last one clearly it is not graphicaly.
answered Dec 9 at 0:44
greedoid
37.7k114794
edited Dec 9 at 0:51
answered Dec 9 at 0:44
greedoid
37.7k114794
answered Dec 9 at 0:44
greedoid
37.7k114794
answered Dec 9 at 0:44
greedoid
37.7k114794
37.7k114794
Can you still get a planar graph even if it's not a simple, connected one based on the formula? I thought that formula was just for simple, connected planar graphs.
– cosmicbrownie
Dec 9 at 0:47
Yes it is, but your graph is clearly connected, it has to many edges to not be connected
– greedoid
Dec 9 at 0:48
add a comment |
Can you still get a planar graph even if it's not a simple, connected one based on the formula? I thought that formula was just for simple, connected planar graphs.
– cosmicbrownie
Dec 9 at 0:47
Yes it is, but your graph is clearly connected, it has to many edges to not be connected
– greedoid
Dec 9 at 0:48
Can you still get a planar graph even if it's not a simple, connected one based on the formula? I thought that formula was just for simple, connected planar graphs.
– cosmicbrownie
Dec 9 at 0:47
Can you still get a planar graph even if it's not a simple, connected one based on the formula? I thought that formula was just for simple, connected planar graphs.
– cosmicbrownie
Dec 9 at 0:47
Yes it is, but your graph is clearly connected, it has to many edges to not be connected
– greedoid
Dec 9 at 0:48
Yes it is, but your graph is clearly connected, it has to many edges to not be connected
– greedoid
Dec 9 at 0:48
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3031861%2fdraw-a-planar-graph-with-two-vertices-of-degree-3-and-four-vertices-of-degree-5%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
Euler's formula counts the external face. Your graph has 9.
– Misha Lavrov
Dec 9 at 2:50
3 minutes. $ $ $ $
– Did
Dec 9 at 10:54
I had no trouble drawing a simple connected planar graph with two vertices of degree $3$ and four vertices of degree $5$. It is a tree of order $22$. (Was there some other condition you didn't mention?)
– bof
Dec 9 at 10:59