Mutually disjoint triangles in certain planar graph
Clash Royale CLAN TAG#URR8PPP
$begingroup$
Let G be a connected, planar graph for which every vertex has degree 3, except that one vertex has degree 2.
Is it possible to construct an example of such G whose only odd faces are triangles, and for which no two such triangles share a common vertex?
(For my purposes I may assume there are no faces of length 1 or 2, in which case there must be an odd face of length at least 3. By the handshake lemma, there are an even number of, hence at least 2, such odd faces.)
combinatorics discrete-mathematics graph-theory
asked Dec 30 '18 at 5:00
FinallysignedupFinallysignedup
666
$endgroup$
add a comment |
$begingroup$
Let G be a connected, planar graph for which every vertex has degree 3, except that one vertex has degree 2.
Is it possible to construct an example of such G whose only odd faces are triangles, and for which no two such triangles share a common vertex?
(For my purposes I may assume there are no faces of length 1 or 2, in which case there must be an odd face of length at least 3. By the handshake lemma, there are an even number of, hence at least 2, such odd faces.)
combinatorics discrete-mathematics graph-theory
asked Dec 30 '18 at 5:00
FinallysignedupFinallysignedup
666
$endgroup$
$begingroup$
For my own edification.. what is an odd face ?
$endgroup$
– T. Ford
Dec 30 '18 at 5:04
$begingroup$
Face with odd number of sides.
$endgroup$
– Zachary Hunter
Dec 30 '18 at 5:09
$begingroup$
I think "those bounded by an odd length cycle" is a sensible definition.
$endgroup$
– Finallysignedup
Dec 30 '18 at 5:11
add a comment |
$begingroup$
Let G be a connected, planar graph for which every vertex has degree 3, except that one vertex has degree 2.
Is it possible to construct an example of such G whose only odd faces are triangles, and for which no two such triangles share a common vertex?
(For my purposes I may assume there are no faces of length 1 or 2, in which case there must be an odd face of length at least 3. By the handshake lemma, there are an even number of, hence at least 2, such odd faces.)
combinatorics discrete-mathematics graph-theory
asked Dec 30 '18 at 5:00
FinallysignedupFinallysignedup
666
$endgroup$
Let G be a connected, planar graph for which every vertex has degree 3, except that one vertex has degree 2.
Is it possible to construct an example of such G whose only odd faces are triangles, and for which no two such triangles share a common vertex?
(For my purposes I may assume there are no faces of length 1 or 2, in which case there must be an odd face of length at least 3. By the handshake lemma, there are an even number of, hence at least 2, such odd faces.)
combinatorics discrete-mathematics graph-theory
combinatorics discrete-mathematics graph-theory
asked Dec 30 '18 at 5:00
FinallysignedupFinallysignedup
666
asked Dec 30 '18 at 5:00
FinallysignedupFinallysignedup
666
edited Dec 30 '18 at 5:07
Finallysignedup
asked Dec 30 '18 at 5:00
FinallysignedupFinallysignedup
666
asked Dec 30 '18 at 5:00
FinallysignedupFinallysignedup
666
asked Dec 30 '18 at 5:00
FinallysignedupFinallysignedup
666
666
$begingroup$
For my own edification.. what is an odd face ?
$endgroup$
– T. Ford
Dec 30 '18 at 5:04
$begingroup$
Face with odd number of sides.
$endgroup$
– Zachary Hunter
Dec 30 '18 at 5:09
$begingroup$
I think "those bounded by an odd length cycle" is a sensible definition.
$endgroup$
– Finallysignedup
Dec 30 '18 at 5:11
add a comment |
$begingroup$
For my own edification.. what is an odd face ?
$endgroup$
– T. Ford
Dec 30 '18 at 5:04
$begingroup$
Face with odd number of sides.
$endgroup$
– Zachary Hunter
Dec 30 '18 at 5:09
$begingroup$
I think "those bounded by an odd length cycle" is a sensible definition.
$endgroup$
– Finallysignedup
Dec 30 '18 at 5:11
$begingroup$
For my own edification.. what is an odd face ?
$endgroup$
– T. Ford
Dec 30 '18 at 5:04
$begingroup$
For my own edification.. what is an odd face ?
$endgroup$
– T. Ford
Dec 30 '18 at 5:04
$begingroup$
Face with odd number of sides.
$endgroup$
– Zachary Hunter
Dec 30 '18 at 5:09
$begingroup$
Face with odd number of sides.
$endgroup$
– Zachary Hunter
Dec 30 '18 at 5:09
$begingroup$
I think "those bounded by an odd length cycle" is a sensible definition.
$endgroup$
– Finallysignedup
Dec 30 '18 at 5:11
$begingroup$
I think "those bounded by an odd length cycle" is a sensible definition.
$endgroup$
– Finallysignedup
Dec 30 '18 at 5:11
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Here is one such graph - or, more precisely, one such plane embedding of a graph, since the lengths of the faces are not properties of the graph itself. It has two faces of length 3 (including the external face), two faces of length 4, and two faces of length 6.
(Motivation: we start with a triangular pyramid, which has all the required properties except for the degree-2 vertex, and modify it a little to make it work.)
answered Dec 30 '18 at 5:14
Misha LavrovMisha Lavrov
44.3k555106
$endgroup$
$begingroup$
Thanks. I now wish to only have degree 3 vertices. I've made a new (hopefully final) question.
$endgroup$
– Finallysignedup
Dec 30 '18 at 6:03
add a comment |
$begingroup$
Take two cycles of the same order 2n+1, $C_a$ and $C_b$ and number each in clockwise fashion.
"Glue together" $v_1a$ and $v_1b$, and then do the same for $v_2a$ and $v_2b$, so that there is just one edge between $v_1$ and $v_2$.
Then, for each $i > 2$ create an edge between $v_ia$ and $v_ib$.
Finally, subdivide the edge between $v_1$ and $v_2$.
answered Dec 30 '18 at 5:17
Zachary HunterZachary Hunter
51111
$endgroup$
$begingroup$
Thanks. Sorry that I could not tick both answers.
$endgroup$
– Finallysignedup
Dec 30 '18 at 6:02
$begingroup$
Understandable, it is the fault of my laziness in creating diagrams.
$endgroup$
– Zachary Hunter
Dec 30 '18 at 6:04
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%2f3056515%2fmutually-disjoint-triangles-in-certain-planar-graph%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
$begingroup$
Here is one such graph - or, more precisely, one such plane embedding of a graph, since the lengths of the faces are not properties of the graph itself. It has two faces of length 3 (including the external face), two faces of length 4, and two faces of length 6.
(Motivation: we start with a triangular pyramid, which has all the required properties except for the degree-2 vertex, and modify it a little to make it work.)
answered Dec 30 '18 at 5:14
Misha LavrovMisha Lavrov
44.3k555106
$endgroup$
$begingroup$
Thanks. I now wish to only have degree 3 vertices. I've made a new (hopefully final) question.
$endgroup$
– Finallysignedup
Dec 30 '18 at 6:03
add a comment |
$begingroup$
Here is one such graph - or, more precisely, one such plane embedding of a graph, since the lengths of the faces are not properties of the graph itself. It has two faces of length 3 (including the external face), two faces of length 4, and two faces of length 6.
(Motivation: we start with a triangular pyramid, which has all the required properties except for the degree-2 vertex, and modify it a little to make it work.)
answered Dec 30 '18 at 5:14
Misha LavrovMisha Lavrov
44.3k555106
$endgroup$
$begingroup$
Thanks. I now wish to only have degree 3 vertices. I've made a new (hopefully final) question.
$endgroup$
– Finallysignedup
Dec 30 '18 at 6:03
add a comment |
$begingroup$
Here is one such graph - or, more precisely, one such plane embedding of a graph, since the lengths of the faces are not properties of the graph itself. It has two faces of length 3 (including the external face), two faces of length 4, and two faces of length 6.
(Motivation: we start with a triangular pyramid, which has all the required properties except for the degree-2 vertex, and modify it a little to make it work.)
answered Dec 30 '18 at 5:14
Misha LavrovMisha Lavrov
44.3k555106
$endgroup$
Here is one such graph - or, more precisely, one such plane embedding of a graph, since the lengths of the faces are not properties of the graph itself. It has two faces of length 3 (including the external face), two faces of length 4, and two faces of length 6.
(Motivation: we start with a triangular pyramid, which has all the required properties except for the degree-2 vertex, and modify it a little to make it work.)
answered Dec 30 '18 at 5:14
Misha LavrovMisha Lavrov
44.3k555106
edited Dec 30 '18 at 15:34
answered Dec 30 '18 at 5:14
Misha LavrovMisha Lavrov
44.3k555106
answered Dec 30 '18 at 5:14
Misha LavrovMisha Lavrov
44.3k555106
answered Dec 30 '18 at 5:14
Misha LavrovMisha Lavrov
44.3k555106
44.3k555106
$begingroup$
Thanks. I now wish to only have degree 3 vertices. I've made a new (hopefully final) question.
$endgroup$
– Finallysignedup
Dec 30 '18 at 6:03
add a comment |
$begingroup$
Thanks. I now wish to only have degree 3 vertices. I've made a new (hopefully final) question.
$endgroup$
– Finallysignedup
Dec 30 '18 at 6:03
$begingroup$
Thanks. I now wish to only have degree 3 vertices. I've made a new (hopefully final) question.
$endgroup$
– Finallysignedup
Dec 30 '18 at 6:03
$begingroup$
Thanks. I now wish to only have degree 3 vertices. I've made a new (hopefully final) question.
$endgroup$
– Finallysignedup
Dec 30 '18 at 6:03
add a comment |
$begingroup$
Take two cycles of the same order 2n+1, $C_a$ and $C_b$ and number each in clockwise fashion.
"Glue together" $v_1a$ and $v_1b$, and then do the same for $v_2a$ and $v_2b$, so that there is just one edge between $v_1$ and $v_2$.
Then, for each $i > 2$ create an edge between $v_ia$ and $v_ib$.
Finally, subdivide the edge between $v_1$ and $v_2$.
answered Dec 30 '18 at 5:17
Zachary HunterZachary Hunter
51111
$endgroup$
$begingroup$
Thanks. Sorry that I could not tick both answers.
$endgroup$
– Finallysignedup
Dec 30 '18 at 6:02
$begingroup$
Understandable, it is the fault of my laziness in creating diagrams.
$endgroup$
– Zachary Hunter
Dec 30 '18 at 6:04
add a comment |
$begingroup$
Take two cycles of the same order 2n+1, $C_a$ and $C_b$ and number each in clockwise fashion.
"Glue together" $v_1a$ and $v_1b$, and then do the same for $v_2a$ and $v_2b$, so that there is just one edge between $v_1$ and $v_2$.
Then, for each $i > 2$ create an edge between $v_ia$ and $v_ib$.
Finally, subdivide the edge between $v_1$ and $v_2$.
answered Dec 30 '18 at 5:17
Zachary HunterZachary Hunter
51111
$endgroup$
$begingroup$
Thanks. Sorry that I could not tick both answers.
$endgroup$
– Finallysignedup
Dec 30 '18 at 6:02
$begingroup$
Understandable, it is the fault of my laziness in creating diagrams.
$endgroup$
– Zachary Hunter
Dec 30 '18 at 6:04
add a comment |
$begingroup$
Take two cycles of the same order 2n+1, $C_a$ and $C_b$ and number each in clockwise fashion.
"Glue together" $v_1a$ and $v_1b$, and then do the same for $v_2a$ and $v_2b$, so that there is just one edge between $v_1$ and $v_2$.
Then, for each $i > 2$ create an edge between $v_ia$ and $v_ib$.
Finally, subdivide the edge between $v_1$ and $v_2$.
answered Dec 30 '18 at 5:17
Zachary HunterZachary Hunter
51111
$endgroup$
Take two cycles of the same order 2n+1, $C_a$ and $C_b$ and number each in clockwise fashion.
"Glue together" $v_1a$ and $v_1b$, and then do the same for $v_2a$ and $v_2b$, so that there is just one edge between $v_1$ and $v_2$.
Then, for each $i > 2$ create an edge between $v_ia$ and $v_ib$.
Finally, subdivide the edge between $v_1$ and $v_2$.
answered Dec 30 '18 at 5:17
Zachary HunterZachary Hunter
51111
answered Dec 30 '18 at 5:17
Zachary HunterZachary Hunter
51111
answered Dec 30 '18 at 5:17
Zachary HunterZachary Hunter
51111
answered Dec 30 '18 at 5:17
Zachary HunterZachary Hunter
51111
51111
$begingroup$
Thanks. Sorry that I could not tick both answers.
$endgroup$
– Finallysignedup
Dec 30 '18 at 6:02
$begingroup$
Understandable, it is the fault of my laziness in creating diagrams.
$endgroup$
– Zachary Hunter
Dec 30 '18 at 6:04
add a comment |
$begingroup$
Thanks. Sorry that I could not tick both answers.
$endgroup$
– Finallysignedup
Dec 30 '18 at 6:02
$begingroup$
Understandable, it is the fault of my laziness in creating diagrams.
$endgroup$
– Zachary Hunter
Dec 30 '18 at 6:04
$begingroup$
Thanks. Sorry that I could not tick both answers.
$endgroup$
– Finallysignedup
Dec 30 '18 at 6:02
$begingroup$
Thanks. Sorry that I could not tick both answers.
$endgroup$
– Finallysignedup
Dec 30 '18 at 6:02
$begingroup$
Understandable, it is the fault of my laziness in creating diagrams.
$endgroup$
– Zachary Hunter
Dec 30 '18 at 6:04
$begingroup$
Understandable, it is the fault of my laziness in creating diagrams.
$endgroup$
– Zachary Hunter
Dec 30 '18 at 6:04
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%2f3056515%2fmutually-disjoint-triangles-in-certain-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
$begingroup$
For my own edification.. what is an odd face ?
$endgroup$
– T. Ford
Dec 30 '18 at 5:04
$begingroup$
Face with odd number of sides.
$endgroup$
– Zachary Hunter
Dec 30 '18 at 5:09
$begingroup$
I think "those bounded by an odd length cycle" is a sensible definition.
$endgroup$
– Finallysignedup
Dec 30 '18 at 5:11