Characterization of platonic graphs
$begingroup$
Problem 2.32 of the Book Combinatorial Optimization asks us to prove, that there are up to isomorphism only $5$ platonic graphs, i.e. $3$-connected, planar, regular graphs whose faces are all bounded by the same number of edges.
Let $G$ be such a graph and say it is $r$-regular and all faces are bounded by $k$ edges. Now it is not too difficult to show using Eulers Formula that there are only $5$ possibilities for the pair $(k,r)$ (corresponding to the $5$ platonic solids of course.) But I think to solve the excersise we have to show that a graph is indeed uniquely determined by these invariants. For example
Why is there up to isomorphism only one $3$-connected, planar,
$5$-regular graph whose faces are all bounded by $3$ edges?
graph-theory planar-graph
asked Nov 9 '18 at 8:12
AlexAlex
894
$endgroup$
|
show 1 more comment
$begingroup$
Problem 2.32 of the Book Combinatorial Optimization asks us to prove, that there are up to isomorphism only $5$ platonic graphs, i.e. $3$-connected, planar, regular graphs whose faces are all bounded by the same number of edges.
Let $G$ be such a graph and say it is $r$-regular and all faces are bounded by $k$ edges. Now it is not too difficult to show using Eulers Formula that there are only $5$ possibilities for the pair $(k,r)$ (corresponding to the $5$ platonic solids of course.) But I think to solve the excersise we have to show that a graph is indeed uniquely determined by these invariants. For example
Why is there up to isomorphism only one $3$-connected, planar,
$5$-regular graph whose faces are all bounded by $3$ edges?
graph-theory planar-graph
asked Nov 9 '18 at 8:12
AlexAlex
894
$endgroup$
$begingroup$
...and why should using Euler's Formula not be enough?
$endgroup$
– draks ...
Nov 9 '18 at 8:16
$begingroup$
Because Eulers Formula only gives a restriction on the pair $(k,r)$ but there could be multiple, non-isomorphic graphs with the same pair.
$endgroup$
– Alex
Nov 9 '18 at 8:17
$begingroup$
maybe you can use symmetries of the graphs?
$endgroup$
– draks ...
Nov 9 '18 at 8:30
$begingroup$
In one graph theory book I read, it was said that to prove there is only one of each possibility is a lot harder than coming up with the list. That book went on to deal with one of them, and another in exercises. So it may be this is a bit difficult to give a formal proof.
$endgroup$
– coffeemath
Nov 9 '18 at 8:36
$begingroup$
@coffeemath Do you remember which book it was?
$endgroup$
– Alex
Nov 9 '18 at 8:49
|
show 1 more comment
$begingroup$
Problem 2.32 of the Book Combinatorial Optimization asks us to prove, that there are up to isomorphism only $5$ platonic graphs, i.e. $3$-connected, planar, regular graphs whose faces are all bounded by the same number of edges.
Let $G$ be such a graph and say it is $r$-regular and all faces are bounded by $k$ edges. Now it is not too difficult to show using Eulers Formula that there are only $5$ possibilities for the pair $(k,r)$ (corresponding to the $5$ platonic solids of course.) But I think to solve the excersise we have to show that a graph is indeed uniquely determined by these invariants. For example
Why is there up to isomorphism only one $3$-connected, planar,
$5$-regular graph whose faces are all bounded by $3$ edges?
graph-theory planar-graph
asked Nov 9 '18 at 8:12
AlexAlex
894
$endgroup$
Problem 2.32 of the Book Combinatorial Optimization asks us to prove, that there are up to isomorphism only $5$ platonic graphs, i.e. $3$-connected, planar, regular graphs whose faces are all bounded by the same number of edges.
Let $G$ be such a graph and say it is $r$-regular and all faces are bounded by $k$ edges. Now it is not too difficult to show using Eulers Formula that there are only $5$ possibilities for the pair $(k,r)$ (corresponding to the $5$ platonic solids of course.) But I think to solve the excersise we have to show that a graph is indeed uniquely determined by these invariants. For example
Why is there up to isomorphism only one $3$-connected, planar,
$5$-regular graph whose faces are all bounded by $3$ edges?
graph-theory planar-graph
graph-theory planar-graph
asked Nov 9 '18 at 8:12
AlexAlex
894
asked Nov 9 '18 at 8:12
AlexAlex
894
edited Nov 9 '18 at 18:51
Alex
asked Nov 9 '18 at 8:12
AlexAlex
894
asked Nov 9 '18 at 8:12
AlexAlex
894
asked Nov 9 '18 at 8:12
AlexAlex
894
894
$begingroup$
...and why should using Euler's Formula not be enough?
$endgroup$
– draks ...
Nov 9 '18 at 8:16
$begingroup$
Because Eulers Formula only gives a restriction on the pair $(k,r)$ but there could be multiple, non-isomorphic graphs with the same pair.
$endgroup$
– Alex
Nov 9 '18 at 8:17
$begingroup$
maybe you can use symmetries of the graphs?
$endgroup$
– draks ...
Nov 9 '18 at 8:30
$begingroup$
In one graph theory book I read, it was said that to prove there is only one of each possibility is a lot harder than coming up with the list. That book went on to deal with one of them, and another in exercises. So it may be this is a bit difficult to give a formal proof.
$endgroup$
– coffeemath
Nov 9 '18 at 8:36
$begingroup$
@coffeemath Do you remember which book it was?
$endgroup$
– Alex
Nov 9 '18 at 8:49
|
show 1 more comment
$begingroup$
...and why should using Euler's Formula not be enough?
$endgroup$
– draks ...
Nov 9 '18 at 8:16
$begingroup$
Because Eulers Formula only gives a restriction on the pair $(k,r)$ but there could be multiple, non-isomorphic graphs with the same pair.
$endgroup$
– Alex
Nov 9 '18 at 8:17
$begingroup$
maybe you can use symmetries of the graphs?
$endgroup$
– draks ...
Nov 9 '18 at 8:30
$begingroup$
In one graph theory book I read, it was said that to prove there is only one of each possibility is a lot harder than coming up with the list. That book went on to deal with one of them, and another in exercises. So it may be this is a bit difficult to give a formal proof.
$endgroup$
– coffeemath
Nov 9 '18 at 8:36
$begingroup$
@coffeemath Do you remember which book it was?
$endgroup$
– Alex
Nov 9 '18 at 8:49
$begingroup$
...and why should using Euler's Formula not be enough?
$endgroup$
– draks ...
Nov 9 '18 at 8:16
$begingroup$
...and why should using Euler's Formula not be enough?
$endgroup$
– draks ...
Nov 9 '18 at 8:16
$begingroup$
Because Eulers Formula only gives a restriction on the pair $(k,r)$ but there could be multiple, non-isomorphic graphs with the same pair.
$endgroup$
– Alex
Nov 9 '18 at 8:17
$begingroup$
Because Eulers Formula only gives a restriction on the pair $(k,r)$ but there could be multiple, non-isomorphic graphs with the same pair.
$endgroup$
– Alex
Nov 9 '18 at 8:17
$begingroup$
maybe you can use symmetries of the graphs?
$endgroup$
– draks ...
Nov 9 '18 at 8:30
$begingroup$
maybe you can use symmetries of the graphs?
$endgroup$
– draks ...
Nov 9 '18 at 8:30
$begingroup$
In one graph theory book I read, it was said that to prove there is only one of each possibility is a lot harder than coming up with the list. That book went on to deal with one of them, and another in exercises. So it may be this is a bit difficult to give a formal proof.
$endgroup$
– coffeemath
Nov 9 '18 at 8:36
$begingroup$
In one graph theory book I read, it was said that to prove there is only one of each possibility is a lot harder than coming up with the list. That book went on to deal with one of them, and another in exercises. So it may be this is a bit difficult to give a formal proof.
$endgroup$
– coffeemath
Nov 9 '18 at 8:36
$begingroup$
@coffeemath Do you remember which book it was?
$endgroup$
– Alex
Nov 9 '18 at 8:49
$begingroup$
@coffeemath Do you remember which book it was?
$endgroup$
– Alex
Nov 9 '18 at 8:49
|
show 1 more comment
1 Answer
1
active
oldest
votes
$begingroup$
Here is mostly an answer. For one case, I don't have a nice argument yet, but I have a link to a brute-force treatment, which might be the best we can do. Thank you for asking this question! A lot of discussions I've read of the Platonic graphs seem to neglect this point entirely. (And in particular, I wouldn't be surprised if the writers of the book you're reading didn't expect you to address this point rigorously in solving the exercise.)
Let a $(k,r)$-graph be a $3$-connected, $r$-regular planar graph whose faces all have length $r$. The Euler's formula argument says that the only cases we need to consider are the $(3,3)$-, $(3,4)$-, $(3,5)$-, $(4,3)$-, and $(5,3)$-graphs; we'll show that each of these is unique.
A $(3,3)$-graph must have $4$ vertices and $6$ edges by Euler's formula. The only such graph is the complete graph. So the $(3,3)$-graph is unique.
A $(4,3)$-graph must have $8$ vertices and $12$ edges by Euler's formula; it is bipartite, because all its faces have even length, and because it is regular, both parts of the bipartition have size $4$. Take the bipartite complement (all the edges between the two parts that are not in the original graph). This is a $1$-regular bipartite graph with $4$ edges, which is unique: it can only be the disjoint union of $4$ edges. So the $(4,3)$-graph is unique as well.
A $3$-connected planar graph has a unique planar embedding, therefore a unique dual, and its dual is also $3$-connected. The dual of a $(3,4)$-graph is a $(4,3)$-graph, and we've proven that there's only one of those. Therefore the $(3,4)$-graph is unique as well.
(Alternatively, $(3,4)$-graph must have $6$ vertices by Euler's formula. Therefore its complement is a $1$-regular graph on $6$ vertices, which can only be the disjoint union of $3$ edges. In fact, this is easier than the cube argument, so maybe we should be using duality the other way to simplify the proof as much as possible.)
For a $(5,3)$-graph, which is supposed to be a dodecahedron, see Lemma 1.1 in this paper ("A convex characterization of the graphs of the dodecahedron and icosahedron" by P.V. Cruyce). It spells out the argument that gets glossed over in many sources as "once we start with any face and build the rest of the graph outwards, there is only one way to finish the job". It is not fun to read.
Finally, by another duality argument, the $(3,5)$-graph is unique, because the dual of a $(3,5)$-graph is a $(5,3)$-graph, and the $(5,3)$-graph is unique.
I have some unfinished thoughts about a simpler argument for one of the last two cases (whichever we decide to handle). For example, we can show that a $(3,5)$-graph either has diameter $2$, or else each vertex has a unique counterpart at distance $3$ from it. The first case ought to be impossible, and the second case gives us some extra structure that should help finish the construction. (For instance, we could delete the vertex and its counterpart, be left with a graph that has $10$ triangular faces and $2$ pentagonal faces, and try to show that it must be the pentagonal antiprism.)
answered Nov 10 '18 at 20:04
Misha LavrovMisha Lavrov
47k657107
$endgroup$
$begingroup$
Thanks. I like the duality argument. This way one only has to deal with one of the large cases and it also makes clear how $3$-connectedness enters the proof. Because to come up with the restriction on $(k,r)$ one really only needs $2$-connectedness, I think.
$endgroup$
– Alex
Nov 10 '18 at 21:23
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%2f2991092%2fcharacterization-of-platonic-graphs%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$
Here is mostly an answer. For one case, I don't have a nice argument yet, but I have a link to a brute-force treatment, which might be the best we can do. Thank you for asking this question! A lot of discussions I've read of the Platonic graphs seem to neglect this point entirely. (And in particular, I wouldn't be surprised if the writers of the book you're reading didn't expect you to address this point rigorously in solving the exercise.)
Let a $(k,r)$-graph be a $3$-connected, $r$-regular planar graph whose faces all have length $r$. The Euler's formula argument says that the only cases we need to consider are the $(3,3)$-, $(3,4)$-, $(3,5)$-, $(4,3)$-, and $(5,3)$-graphs; we'll show that each of these is unique.
A $(3,3)$-graph must have $4$ vertices and $6$ edges by Euler's formula. The only such graph is the complete graph. So the $(3,3)$-graph is unique.
A $(4,3)$-graph must have $8$ vertices and $12$ edges by Euler's formula; it is bipartite, because all its faces have even length, and because it is regular, both parts of the bipartition have size $4$. Take the bipartite complement (all the edges between the two parts that are not in the original graph). This is a $1$-regular bipartite graph with $4$ edges, which is unique: it can only be the disjoint union of $4$ edges. So the $(4,3)$-graph is unique as well.
A $3$-connected planar graph has a unique planar embedding, therefore a unique dual, and its dual is also $3$-connected. The dual of a $(3,4)$-graph is a $(4,3)$-graph, and we've proven that there's only one of those. Therefore the $(3,4)$-graph is unique as well.
(Alternatively, $(3,4)$-graph must have $6$ vertices by Euler's formula. Therefore its complement is a $1$-regular graph on $6$ vertices, which can only be the disjoint union of $3$ edges. In fact, this is easier than the cube argument, so maybe we should be using duality the other way to simplify the proof as much as possible.)
For a $(5,3)$-graph, which is supposed to be a dodecahedron, see Lemma 1.1 in this paper ("A convex characterization of the graphs of the dodecahedron and icosahedron" by P.V. Cruyce). It spells out the argument that gets glossed over in many sources as "once we start with any face and build the rest of the graph outwards, there is only one way to finish the job". It is not fun to read.
Finally, by another duality argument, the $(3,5)$-graph is unique, because the dual of a $(3,5)$-graph is a $(5,3)$-graph, and the $(5,3)$-graph is unique.
I have some unfinished thoughts about a simpler argument for one of the last two cases (whichever we decide to handle). For example, we can show that a $(3,5)$-graph either has diameter $2$, or else each vertex has a unique counterpart at distance $3$ from it. The first case ought to be impossible, and the second case gives us some extra structure that should help finish the construction. (For instance, we could delete the vertex and its counterpart, be left with a graph that has $10$ triangular faces and $2$ pentagonal faces, and try to show that it must be the pentagonal antiprism.)
answered Nov 10 '18 at 20:04
Misha LavrovMisha Lavrov
47k657107
$endgroup$
$begingroup$
Thanks. I like the duality argument. This way one only has to deal with one of the large cases and it also makes clear how $3$-connectedness enters the proof. Because to come up with the restriction on $(k,r)$ one really only needs $2$-connectedness, I think.
$endgroup$
– Alex
Nov 10 '18 at 21:23
add a comment |
$begingroup$
Here is mostly an answer. For one case, I don't have a nice argument yet, but I have a link to a brute-force treatment, which might be the best we can do. Thank you for asking this question! A lot of discussions I've read of the Platonic graphs seem to neglect this point entirely. (And in particular, I wouldn't be surprised if the writers of the book you're reading didn't expect you to address this point rigorously in solving the exercise.)
Let a $(k,r)$-graph be a $3$-connected, $r$-regular planar graph whose faces all have length $r$. The Euler's formula argument says that the only cases we need to consider are the $(3,3)$-, $(3,4)$-, $(3,5)$-, $(4,3)$-, and $(5,3)$-graphs; we'll show that each of these is unique.
A $(3,3)$-graph must have $4$ vertices and $6$ edges by Euler's formula. The only such graph is the complete graph. So the $(3,3)$-graph is unique.
A $(4,3)$-graph must have $8$ vertices and $12$ edges by Euler's formula; it is bipartite, because all its faces have even length, and because it is regular, both parts of the bipartition have size $4$. Take the bipartite complement (all the edges between the two parts that are not in the original graph). This is a $1$-regular bipartite graph with $4$ edges, which is unique: it can only be the disjoint union of $4$ edges. So the $(4,3)$-graph is unique as well.
A $3$-connected planar graph has a unique planar embedding, therefore a unique dual, and its dual is also $3$-connected. The dual of a $(3,4)$-graph is a $(4,3)$-graph, and we've proven that there's only one of those. Therefore the $(3,4)$-graph is unique as well.
(Alternatively, $(3,4)$-graph must have $6$ vertices by Euler's formula. Therefore its complement is a $1$-regular graph on $6$ vertices, which can only be the disjoint union of $3$ edges. In fact, this is easier than the cube argument, so maybe we should be using duality the other way to simplify the proof as much as possible.)
For a $(5,3)$-graph, which is supposed to be a dodecahedron, see Lemma 1.1 in this paper ("A convex characterization of the graphs of the dodecahedron and icosahedron" by P.V. Cruyce). It spells out the argument that gets glossed over in many sources as "once we start with any face and build the rest of the graph outwards, there is only one way to finish the job". It is not fun to read.
Finally, by another duality argument, the $(3,5)$-graph is unique, because the dual of a $(3,5)$-graph is a $(5,3)$-graph, and the $(5,3)$-graph is unique.
I have some unfinished thoughts about a simpler argument for one of the last two cases (whichever we decide to handle). For example, we can show that a $(3,5)$-graph either has diameter $2$, or else each vertex has a unique counterpart at distance $3$ from it. The first case ought to be impossible, and the second case gives us some extra structure that should help finish the construction. (For instance, we could delete the vertex and its counterpart, be left with a graph that has $10$ triangular faces and $2$ pentagonal faces, and try to show that it must be the pentagonal antiprism.)
answered Nov 10 '18 at 20:04
Misha LavrovMisha Lavrov
47k657107
$endgroup$
$begingroup$
Thanks. I like the duality argument. This way one only has to deal with one of the large cases and it also makes clear how $3$-connectedness enters the proof. Because to come up with the restriction on $(k,r)$ one really only needs $2$-connectedness, I think.
$endgroup$
– Alex
Nov 10 '18 at 21:23
add a comment |
$begingroup$
Here is mostly an answer. For one case, I don't have a nice argument yet, but I have a link to a brute-force treatment, which might be the best we can do. Thank you for asking this question! A lot of discussions I've read of the Platonic graphs seem to neglect this point entirely. (And in particular, I wouldn't be surprised if the writers of the book you're reading didn't expect you to address this point rigorously in solving the exercise.)
Let a $(k,r)$-graph be a $3$-connected, $r$-regular planar graph whose faces all have length $r$. The Euler's formula argument says that the only cases we need to consider are the $(3,3)$-, $(3,4)$-, $(3,5)$-, $(4,3)$-, and $(5,3)$-graphs; we'll show that each of these is unique.
A $(3,3)$-graph must have $4$ vertices and $6$ edges by Euler's formula. The only such graph is the complete graph. So the $(3,3)$-graph is unique.
A $(4,3)$-graph must have $8$ vertices and $12$ edges by Euler's formula; it is bipartite, because all its faces have even length, and because it is regular, both parts of the bipartition have size $4$. Take the bipartite complement (all the edges between the two parts that are not in the original graph). This is a $1$-regular bipartite graph with $4$ edges, which is unique: it can only be the disjoint union of $4$ edges. So the $(4,3)$-graph is unique as well.
A $3$-connected planar graph has a unique planar embedding, therefore a unique dual, and its dual is also $3$-connected. The dual of a $(3,4)$-graph is a $(4,3)$-graph, and we've proven that there's only one of those. Therefore the $(3,4)$-graph is unique as well.
(Alternatively, $(3,4)$-graph must have $6$ vertices by Euler's formula. Therefore its complement is a $1$-regular graph on $6$ vertices, which can only be the disjoint union of $3$ edges. In fact, this is easier than the cube argument, so maybe we should be using duality the other way to simplify the proof as much as possible.)
For a $(5,3)$-graph, which is supposed to be a dodecahedron, see Lemma 1.1 in this paper ("A convex characterization of the graphs of the dodecahedron and icosahedron" by P.V. Cruyce). It spells out the argument that gets glossed over in many sources as "once we start with any face and build the rest of the graph outwards, there is only one way to finish the job". It is not fun to read.
Finally, by another duality argument, the $(3,5)$-graph is unique, because the dual of a $(3,5)$-graph is a $(5,3)$-graph, and the $(5,3)$-graph is unique.
I have some unfinished thoughts about a simpler argument for one of the last two cases (whichever we decide to handle). For example, we can show that a $(3,5)$-graph either has diameter $2$, or else each vertex has a unique counterpart at distance $3$ from it. The first case ought to be impossible, and the second case gives us some extra structure that should help finish the construction. (For instance, we could delete the vertex and its counterpart, be left with a graph that has $10$ triangular faces and $2$ pentagonal faces, and try to show that it must be the pentagonal antiprism.)
answered Nov 10 '18 at 20:04
Misha LavrovMisha Lavrov
47k657107
$endgroup$
Here is mostly an answer. For one case, I don't have a nice argument yet, but I have a link to a brute-force treatment, which might be the best we can do. Thank you for asking this question! A lot of discussions I've read of the Platonic graphs seem to neglect this point entirely. (And in particular, I wouldn't be surprised if the writers of the book you're reading didn't expect you to address this point rigorously in solving the exercise.)
Let a $(k,r)$-graph be a $3$-connected, $r$-regular planar graph whose faces all have length $r$. The Euler's formula argument says that the only cases we need to consider are the $(3,3)$-, $(3,4)$-, $(3,5)$-, $(4,3)$-, and $(5,3)$-graphs; we'll show that each of these is unique.
A $(3,3)$-graph must have $4$ vertices and $6$ edges by Euler's formula. The only such graph is the complete graph. So the $(3,3)$-graph is unique.
A $(4,3)$-graph must have $8$ vertices and $12$ edges by Euler's formula; it is bipartite, because all its faces have even length, and because it is regular, both parts of the bipartition have size $4$. Take the bipartite complement (all the edges between the two parts that are not in the original graph). This is a $1$-regular bipartite graph with $4$ edges, which is unique: it can only be the disjoint union of $4$ edges. So the $(4,3)$-graph is unique as well.
A $3$-connected planar graph has a unique planar embedding, therefore a unique dual, and its dual is also $3$-connected. The dual of a $(3,4)$-graph is a $(4,3)$-graph, and we've proven that there's only one of those. Therefore the $(3,4)$-graph is unique as well.
(Alternatively, $(3,4)$-graph must have $6$ vertices by Euler's formula. Therefore its complement is a $1$-regular graph on $6$ vertices, which can only be the disjoint union of $3$ edges. In fact, this is easier than the cube argument, so maybe we should be using duality the other way to simplify the proof as much as possible.)
For a $(5,3)$-graph, which is supposed to be a dodecahedron, see Lemma 1.1 in this paper ("A convex characterization of the graphs of the dodecahedron and icosahedron" by P.V. Cruyce). It spells out the argument that gets glossed over in many sources as "once we start with any face and build the rest of the graph outwards, there is only one way to finish the job". It is not fun to read.
Finally, by another duality argument, the $(3,5)$-graph is unique, because the dual of a $(3,5)$-graph is a $(5,3)$-graph, and the $(5,3)$-graph is unique.
I have some unfinished thoughts about a simpler argument for one of the last two cases (whichever we decide to handle). For example, we can show that a $(3,5)$-graph either has diameter $2$, or else each vertex has a unique counterpart at distance $3$ from it. The first case ought to be impossible, and the second case gives us some extra structure that should help finish the construction. (For instance, we could delete the vertex and its counterpart, be left with a graph that has $10$ triangular faces and $2$ pentagonal faces, and try to show that it must be the pentagonal antiprism.)
answered Nov 10 '18 at 20:04
Misha LavrovMisha Lavrov
47k657107
edited Nov 11 '18 at 3:42
answered Nov 10 '18 at 20:04
Misha LavrovMisha Lavrov
47k657107
answered Nov 10 '18 at 20:04
Misha LavrovMisha Lavrov
47k657107
answered Nov 10 '18 at 20:04
Misha LavrovMisha Lavrov
47k657107
47k657107
$begingroup$
Thanks. I like the duality argument. This way one only has to deal with one of the large cases and it also makes clear how $3$-connectedness enters the proof. Because to come up with the restriction on $(k,r)$ one really only needs $2$-connectedness, I think.
$endgroup$
– Alex
Nov 10 '18 at 21:23
add a comment |
$begingroup$
Thanks. I like the duality argument. This way one only has to deal with one of the large cases and it also makes clear how $3$-connectedness enters the proof. Because to come up with the restriction on $(k,r)$ one really only needs $2$-connectedness, I think.
$endgroup$
– Alex
Nov 10 '18 at 21:23
$begingroup$
Thanks. I like the duality argument. This way one only has to deal with one of the large cases and it also makes clear how $3$-connectedness enters the proof. Because to come up with the restriction on $(k,r)$ one really only needs $2$-connectedness, I think.
$endgroup$
– Alex
Nov 10 '18 at 21:23
$begingroup$
Thanks. I like the duality argument. This way one only has to deal with one of the large cases and it also makes clear how $3$-connectedness enters the proof. Because to come up with the restriction on $(k,r)$ one really only needs $2$-connectedness, I think.
$endgroup$
– Alex
Nov 10 '18 at 21:23
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%2f2991092%2fcharacterization-of-platonic-graphs%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$
...and why should using Euler's Formula not be enough?
$endgroup$
– draks ...
Nov 9 '18 at 8:16
$begingroup$
Because Eulers Formula only gives a restriction on the pair $(k,r)$ but there could be multiple, non-isomorphic graphs with the same pair.
$endgroup$
– Alex
Nov 9 '18 at 8:17
$begingroup$
maybe you can use symmetries of the graphs?
$endgroup$
– draks ...
Nov 9 '18 at 8:30
$begingroup$
In one graph theory book I read, it was said that to prove there is only one of each possibility is a lot harder than coming up with the list. That book went on to deal with one of them, and another in exercises. So it may be this is a bit difficult to give a formal proof.
$endgroup$
– coffeemath
Nov 9 '18 at 8:36
$begingroup$
@coffeemath Do you remember which book it was?
$endgroup$
– Alex
Nov 9 '18 at 8:49