Conditions on face length in planar graph
$begingroup$
I have a planar, connected graph with vertices of degree 3 except for one with degree 2. There is an odd, outer face of length at least 5, containing the degree 2 vertex. The inside faces consist of 3 mutually disjoint triangles,disjoint from the outer face, and the rest even.
EDIT: further suppose that no triangle and square share an edge. (Adjacent squares are permitted.)
Is such a graph possible?
Below is a non-example. It only has 1 triangle, and this is not disjoint from the outer, length 5, face (which contains the degree 2 vertex). Plus there is a square sharing an edge with a triangle.
combinatorics discrete-mathematics graph-theory
asked Dec 30 '18 at 13:43
FinallysignedupFinallysignedup
666
$endgroup$
add a comment |
$begingroup$
I have a planar, connected graph with vertices of degree 3 except for one with degree 2. There is an odd, outer face of length at least 5, containing the degree 2 vertex. The inside faces consist of 3 mutually disjoint triangles,disjoint from the outer face, and the rest even.
EDIT: further suppose that no triangle and square share an edge. (Adjacent squares are permitted.)
Is such a graph possible?
Below is a non-example. It only has 1 triangle, and this is not disjoint from the outer, length 5, face (which contains the degree 2 vertex). Plus there is a square sharing an edge with a triangle.
combinatorics discrete-mathematics graph-theory
asked Dec 30 '18 at 13:43
FinallysignedupFinallysignedup
666
$endgroup$
add a comment |
$begingroup$
I have a planar, connected graph with vertices of degree 3 except for one with degree 2. There is an odd, outer face of length at least 5, containing the degree 2 vertex. The inside faces consist of 3 mutually disjoint triangles,disjoint from the outer face, and the rest even.
EDIT: further suppose that no triangle and square share an edge. (Adjacent squares are permitted.)
Is such a graph possible?
Below is a non-example. It only has 1 triangle, and this is not disjoint from the outer, length 5, face (which contains the degree 2 vertex). Plus there is a square sharing an edge with a triangle.
combinatorics discrete-mathematics graph-theory
asked Dec 30 '18 at 13:43
FinallysignedupFinallysignedup
666
$endgroup$
I have a planar, connected graph with vertices of degree 3 except for one with degree 2. There is an odd, outer face of length at least 5, containing the degree 2 vertex. The inside faces consist of 3 mutually disjoint triangles,disjoint from the outer face, and the rest even.
EDIT: further suppose that no triangle and square share an edge. (Adjacent squares are permitted.)
Is such a graph possible?
Below is a non-example. It only has 1 triangle, and this is not disjoint from the outer, length 5, face (which contains the degree 2 vertex). Plus there is a square sharing an edge with a triangle.
combinatorics discrete-mathematics graph-theory
combinatorics discrete-mathematics graph-theory
asked Dec 30 '18 at 13:43
FinallysignedupFinallysignedup
666
asked Dec 30 '18 at 13:43
FinallysignedupFinallysignedup
666
edited Dec 31 '18 at 10:54
Finallysignedup
asked Dec 30 '18 at 13:43
FinallysignedupFinallysignedup
666
asked Dec 30 '18 at 13:43
FinallysignedupFinallysignedup
666
asked Dec 30 '18 at 13:43
FinallysignedupFinallysignedup
666
666
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The plan:
- Start with a 3-regular planar graph which has 4 triangular faces and a bunch of even faces.
- Subdivide an edge between a triangular face and an even face. That face becomes the external odd face, and the triangular face now has length 4. (But the three other triangular faces remain intact.)
- The other triangular faces might touch the odd face, or each other. To fix this, subdivide them as shown in the diagram below (adding the edges in red). This leaves one triangular face, creates two length-4 faces, and leaves the parity of adjacent faces unchanged. We can do this in three different directions, and we should choose one that moves the triangle away from the face it's not supposed to be touching. Repeat this until the triangles are disjoint from everything they're supposed to be disjoint from.
For example, if we do this to the truncated tetrahedron (with three triangular and three hexagonal faces) we get the graph below:
If you are likely to have more such questions, you should be looking at the general principles at work here. To figure out this plan, we work backwards, simplifying the conditions required one at a time.
The degree-2 vertex is awkward, so let's look at what happens when we smooth it out (deleting it and connecting its neighbors by an edge directly). Then the odd exterior face becomes even, and the interior even face becomes odd. So now we have a 3-regular planar graph with 4 odd faces, at least 3 of them triangles. (All four of them might as well be triangles.)
The condition that the triangular faces be disjoint to each other and to the external face is awkward. So we develop a construction that lets us push a triangular face away from an exterior face. Now that condition goes away.
Finally, it's easy to find 3-regular planar graphs with the right number of faces among various polyhedral graphs, so those should be the places you start looking.
Step 3 of the plan can be changed to replace each triangle with the structure below:
(When we add it, the length of each face adjacent to the former triangle increases by 2, so the parity does not change.)
This not only makes sure that no triangles are adjacent, but also that each triangle is only adjacent to hexagons.
answered Dec 30 '18 at 16:05
Misha LavrovMisha Lavrov
47.8k657107
$endgroup$
$begingroup$
Thanks, especially for the pedagogy. Based on these techniques it seems that (assuming above hypotheses) that a square and a triangle must share an edge, no? (This would be sufficient for my purposes.)
$endgroup$
– Finallysignedup
Dec 31 '18 at 10:46
$begingroup$
I’ve added this condition to the question.
$endgroup$
– Finallysignedup
Dec 31 '18 at 10:56
1
$begingroup$
I've addressed this condition, but maybe you can share whatever is driving you to add these extra conditions? Rather than saying "yes, is possible" to each of your questions, it might be best to address the underlying problem.
$endgroup$
– Misha Lavrov
Dec 31 '18 at 16:01
1
$begingroup$
@MishaLavrov You are suggesting (correctly, I think) that the OP is asking an xy question: en.wikipedia.org/wiki/XY_problem,
$endgroup$
– Ethan Bolker
Dec 31 '18 at 16:12
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%2f3056845%2fconditions-on-face-length-in-planar-graph%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The plan:
- Start with a 3-regular planar graph which has 4 triangular faces and a bunch of even faces.
- Subdivide an edge between a triangular face and an even face. That face becomes the external odd face, and the triangular face now has length 4. (But the three other triangular faces remain intact.)
- The other triangular faces might touch the odd face, or each other. To fix this, subdivide them as shown in the diagram below (adding the edges in red). This leaves one triangular face, creates two length-4 faces, and leaves the parity of adjacent faces unchanged. We can do this in three different directions, and we should choose one that moves the triangle away from the face it's not supposed to be touching. Repeat this until the triangles are disjoint from everything they're supposed to be disjoint from.
For example, if we do this to the truncated tetrahedron (with three triangular and three hexagonal faces) we get the graph below:
If you are likely to have more such questions, you should be looking at the general principles at work here. To figure out this plan, we work backwards, simplifying the conditions required one at a time.
The degree-2 vertex is awkward, so let's look at what happens when we smooth it out (deleting it and connecting its neighbors by an edge directly). Then the odd exterior face becomes even, and the interior even face becomes odd. So now we have a 3-regular planar graph with 4 odd faces, at least 3 of them triangles. (All four of them might as well be triangles.)
The condition that the triangular faces be disjoint to each other and to the external face is awkward. So we develop a construction that lets us push a triangular face away from an exterior face. Now that condition goes away.
Finally, it's easy to find 3-regular planar graphs with the right number of faces among various polyhedral graphs, so those should be the places you start looking.
Step 3 of the plan can be changed to replace each triangle with the structure below:
(When we add it, the length of each face adjacent to the former triangle increases by 2, so the parity does not change.)
This not only makes sure that no triangles are adjacent, but also that each triangle is only adjacent to hexagons.
answered Dec 30 '18 at 16:05
Misha LavrovMisha Lavrov
47.8k657107
$endgroup$
$begingroup$
Thanks, especially for the pedagogy. Based on these techniques it seems that (assuming above hypotheses) that a square and a triangle must share an edge, no? (This would be sufficient for my purposes.)
$endgroup$
– Finallysignedup
Dec 31 '18 at 10:46
$begingroup$
I’ve added this condition to the question.
$endgroup$
– Finallysignedup
Dec 31 '18 at 10:56
1
$begingroup$
I've addressed this condition, but maybe you can share whatever is driving you to add these extra conditions? Rather than saying "yes, is possible" to each of your questions, it might be best to address the underlying problem.
$endgroup$
– Misha Lavrov
Dec 31 '18 at 16:01
1
$begingroup$
@MishaLavrov You are suggesting (correctly, I think) that the OP is asking an xy question: en.wikipedia.org/wiki/XY_problem,
$endgroup$
– Ethan Bolker
Dec 31 '18 at 16:12
add a comment |
$begingroup$
The plan:
- Start with a 3-regular planar graph which has 4 triangular faces and a bunch of even faces.
- Subdivide an edge between a triangular face and an even face. That face becomes the external odd face, and the triangular face now has length 4. (But the three other triangular faces remain intact.)
- The other triangular faces might touch the odd face, or each other. To fix this, subdivide them as shown in the diagram below (adding the edges in red). This leaves one triangular face, creates two length-4 faces, and leaves the parity of adjacent faces unchanged. We can do this in three different directions, and we should choose one that moves the triangle away from the face it's not supposed to be touching. Repeat this until the triangles are disjoint from everything they're supposed to be disjoint from.
For example, if we do this to the truncated tetrahedron (with three triangular and three hexagonal faces) we get the graph below:
If you are likely to have more such questions, you should be looking at the general principles at work here. To figure out this plan, we work backwards, simplifying the conditions required one at a time.
The degree-2 vertex is awkward, so let's look at what happens when we smooth it out (deleting it and connecting its neighbors by an edge directly). Then the odd exterior face becomes even, and the interior even face becomes odd. So now we have a 3-regular planar graph with 4 odd faces, at least 3 of them triangles. (All four of them might as well be triangles.)
The condition that the triangular faces be disjoint to each other and to the external face is awkward. So we develop a construction that lets us push a triangular face away from an exterior face. Now that condition goes away.
Finally, it's easy to find 3-regular planar graphs with the right number of faces among various polyhedral graphs, so those should be the places you start looking.
Step 3 of the plan can be changed to replace each triangle with the structure below:
(When we add it, the length of each face adjacent to the former triangle increases by 2, so the parity does not change.)
This not only makes sure that no triangles are adjacent, but also that each triangle is only adjacent to hexagons.
answered Dec 30 '18 at 16:05
Misha LavrovMisha Lavrov
47.8k657107
$endgroup$
$begingroup$
Thanks, especially for the pedagogy. Based on these techniques it seems that (assuming above hypotheses) that a square and a triangle must share an edge, no? (This would be sufficient for my purposes.)
$endgroup$
– Finallysignedup
Dec 31 '18 at 10:46
$begingroup$
I’ve added this condition to the question.
$endgroup$
– Finallysignedup
Dec 31 '18 at 10:56
1
$begingroup$
I've addressed this condition, but maybe you can share whatever is driving you to add these extra conditions? Rather than saying "yes, is possible" to each of your questions, it might be best to address the underlying problem.
$endgroup$
– Misha Lavrov
Dec 31 '18 at 16:01
1
$begingroup$
@MishaLavrov You are suggesting (correctly, I think) that the OP is asking an xy question: en.wikipedia.org/wiki/XY_problem,
$endgroup$
– Ethan Bolker
Dec 31 '18 at 16:12
add a comment |
$begingroup$
The plan:
- Start with a 3-regular planar graph which has 4 triangular faces and a bunch of even faces.
- Subdivide an edge between a triangular face and an even face. That face becomes the external odd face, and the triangular face now has length 4. (But the three other triangular faces remain intact.)
- The other triangular faces might touch the odd face, or each other. To fix this, subdivide them as shown in the diagram below (adding the edges in red). This leaves one triangular face, creates two length-4 faces, and leaves the parity of adjacent faces unchanged. We can do this in three different directions, and we should choose one that moves the triangle away from the face it's not supposed to be touching. Repeat this until the triangles are disjoint from everything they're supposed to be disjoint from.
For example, if we do this to the truncated tetrahedron (with three triangular and three hexagonal faces) we get the graph below:
If you are likely to have more such questions, you should be looking at the general principles at work here. To figure out this plan, we work backwards, simplifying the conditions required one at a time.
The degree-2 vertex is awkward, so let's look at what happens when we smooth it out (deleting it and connecting its neighbors by an edge directly). Then the odd exterior face becomes even, and the interior even face becomes odd. So now we have a 3-regular planar graph with 4 odd faces, at least 3 of them triangles. (All four of them might as well be triangles.)
The condition that the triangular faces be disjoint to each other and to the external face is awkward. So we develop a construction that lets us push a triangular face away from an exterior face. Now that condition goes away.
Finally, it's easy to find 3-regular planar graphs with the right number of faces among various polyhedral graphs, so those should be the places you start looking.
Step 3 of the plan can be changed to replace each triangle with the structure below:
(When we add it, the length of each face adjacent to the former triangle increases by 2, so the parity does not change.)
This not only makes sure that no triangles are adjacent, but also that each triangle is only adjacent to hexagons.
answered Dec 30 '18 at 16:05
Misha LavrovMisha Lavrov
47.8k657107
$endgroup$
The plan:
- Start with a 3-regular planar graph which has 4 triangular faces and a bunch of even faces.
- Subdivide an edge between a triangular face and an even face. That face becomes the external odd face, and the triangular face now has length 4. (But the three other triangular faces remain intact.)
- The other triangular faces might touch the odd face, or each other. To fix this, subdivide them as shown in the diagram below (adding the edges in red). This leaves one triangular face, creates two length-4 faces, and leaves the parity of adjacent faces unchanged. We can do this in three different directions, and we should choose one that moves the triangle away from the face it's not supposed to be touching. Repeat this until the triangles are disjoint from everything they're supposed to be disjoint from.
For example, if we do this to the truncated tetrahedron (with three triangular and three hexagonal faces) we get the graph below:
If you are likely to have more such questions, you should be looking at the general principles at work here. To figure out this plan, we work backwards, simplifying the conditions required one at a time.
The degree-2 vertex is awkward, so let's look at what happens when we smooth it out (deleting it and connecting its neighbors by an edge directly). Then the odd exterior face becomes even, and the interior even face becomes odd. So now we have a 3-regular planar graph with 4 odd faces, at least 3 of them triangles. (All four of them might as well be triangles.)
The condition that the triangular faces be disjoint to each other and to the external face is awkward. So we develop a construction that lets us push a triangular face away from an exterior face. Now that condition goes away.
Finally, it's easy to find 3-regular planar graphs with the right number of faces among various polyhedral graphs, so those should be the places you start looking.
Step 3 of the plan can be changed to replace each triangle with the structure below:
(When we add it, the length of each face adjacent to the former triangle increases by 2, so the parity does not change.)
This not only makes sure that no triangles are adjacent, but also that each triangle is only adjacent to hexagons.
answered Dec 30 '18 at 16:05
Misha LavrovMisha Lavrov
47.8k657107
edited Dec 31 '18 at 16:00
answered Dec 30 '18 at 16:05
Misha LavrovMisha Lavrov
47.8k657107
answered Dec 30 '18 at 16:05
Misha LavrovMisha Lavrov
47.8k657107
answered Dec 30 '18 at 16:05
Misha LavrovMisha Lavrov
47.8k657107
47.8k657107
$begingroup$
Thanks, especially for the pedagogy. Based on these techniques it seems that (assuming above hypotheses) that a square and a triangle must share an edge, no? (This would be sufficient for my purposes.)
$endgroup$
– Finallysignedup
Dec 31 '18 at 10:46
$begingroup$
I’ve added this condition to the question.
$endgroup$
– Finallysignedup
Dec 31 '18 at 10:56
1
$begingroup$
I've addressed this condition, but maybe you can share whatever is driving you to add these extra conditions? Rather than saying "yes, is possible" to each of your questions, it might be best to address the underlying problem.
$endgroup$
– Misha Lavrov
Dec 31 '18 at 16:01
1
$begingroup$
@MishaLavrov You are suggesting (correctly, I think) that the OP is asking an xy question: en.wikipedia.org/wiki/XY_problem,
$endgroup$
– Ethan Bolker
Dec 31 '18 at 16:12
add a comment |
$begingroup$
Thanks, especially for the pedagogy. Based on these techniques it seems that (assuming above hypotheses) that a square and a triangle must share an edge, no? (This would be sufficient for my purposes.)
$endgroup$
– Finallysignedup
Dec 31 '18 at 10:46
$begingroup$
I’ve added this condition to the question.
$endgroup$
– Finallysignedup
Dec 31 '18 at 10:56
1
$begingroup$
I've addressed this condition, but maybe you can share whatever is driving you to add these extra conditions? Rather than saying "yes, is possible" to each of your questions, it might be best to address the underlying problem.
$endgroup$
– Misha Lavrov
Dec 31 '18 at 16:01
1
$begingroup$
@MishaLavrov You are suggesting (correctly, I think) that the OP is asking an xy question: en.wikipedia.org/wiki/XY_problem,
$endgroup$
– Ethan Bolker
Dec 31 '18 at 16:12
$begingroup$
Thanks, especially for the pedagogy. Based on these techniques it seems that (assuming above hypotheses) that a square and a triangle must share an edge, no? (This would be sufficient for my purposes.)
$endgroup$
– Finallysignedup
Dec 31 '18 at 10:46
$begingroup$
Thanks, especially for the pedagogy. Based on these techniques it seems that (assuming above hypotheses) that a square and a triangle must share an edge, no? (This would be sufficient for my purposes.)
$endgroup$
– Finallysignedup
Dec 31 '18 at 10:46
$begingroup$
I’ve added this condition to the question.
$endgroup$
– Finallysignedup
Dec 31 '18 at 10:56
$begingroup$
I’ve added this condition to the question.
$endgroup$
– Finallysignedup
Dec 31 '18 at 10:56
1
1
$begingroup$
I've addressed this condition, but maybe you can share whatever is driving you to add these extra conditions? Rather than saying "yes, is possible" to each of your questions, it might be best to address the underlying problem.
$endgroup$
– Misha Lavrov
Dec 31 '18 at 16:01
$begingroup$
I've addressed this condition, but maybe you can share whatever is driving you to add these extra conditions? Rather than saying "yes, is possible" to each of your questions, it might be best to address the underlying problem.
$endgroup$
– Misha Lavrov
Dec 31 '18 at 16:01
1
1
$begingroup$
@MishaLavrov You are suggesting (correctly, I think) that the OP is asking an xy question: en.wikipedia.org/wiki/XY_problem,
$endgroup$
– Ethan Bolker
Dec 31 '18 at 16:12
$begingroup$
@MishaLavrov You are suggesting (correctly, I think) that the OP is asking an xy question: en.wikipedia.org/wiki/XY_problem,
$endgroup$
– Ethan Bolker
Dec 31 '18 at 16:12
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%2f3056845%2fconditions-on-face-length-in-planar-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
