Characterization of platonic graphs 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?

 A: 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.)
