8
$\begingroup$

So my problem is:

Prove that the icosahedron graph of Figure 1.2.5 is the only maximal planar graph that is regular of degree $5$.

enter image description here

Here are my $3$ solutions:

Proof -- Version 1

By the Theorem 8.1.8, a maximal planar graph with $p$ vertices (with $p \geq 4$) and $q$ edges must satisfy following equation \begin{equation} 3 p_{3}+2 p_{4}+p_{5}=12+p_{7}+2 p_{8}+3 p_{9}+4 p_{10}+\ldots, \end{equation} where $p_i$ is the number of vertices of degree $i$. In the case of $5$-regular graphs, we know that $p_i = 0$ if $i \neq 5$; so, by the above equation \begin{equation} p=p_{5}=12 . \end{equation} Next, simply observe, that in the case of maximal planar regular graphs, the number of vertices is essentially the determinant of the graph, i.e. there is at most one maximal planar graph with a given number of vertices. This is the case, because we are bounded to have only triangular regions, the number of edges (by the Theorem 8.1.2) $q = 3p-6$ is fixed and the number of regions (by the Theorem 8.1.1) $r = 2-p+q=2-p+(3p-6)=2p-4$ is thus fixed as well. Hence, for maximal planar graphs $p$ is the determinant.

Remark: Another way to think about this would be the following: To construct the $k$-regular maximal planar graph, we determine $p$ by the Theorem 8.1.8, and simply draw the $p$ vertices and add edges arbitrarily, until every vertex is of degree $k$. Because every vertex is equivalent (or isomorphic) to every other vertex of the resulting graph, and since for the given $k$, $p$, $q$ and $r$ are determined, all of the graphs resulting from this procedure must be isomorphic (even though some of them will not be the plane drawing of this graph). [One can also approach this by imagining a grid with $p$ grid-points, each of which must be connected to $k$ grid points and continue by the implementation of the above-mentioned theorems.]

So, we know that we have no "room for extra consideration," because $p=p_5 = 12$ is the only maximal planar $5$-regular graph -- the icosahedron.

Q.E.D.

Side-note: It is interesting to note, that the Theorem 8.1.8 not only tells us about the uniqueness of the maximal planar $k$-regular graph for the given $k$, but also implies that there can only be $3$ such graphs: for $k=3$ it is the tetrahedron; for $k=4$ it is the octahedron; for $k=5$ it is the icosahedron. This is due to the fact that the first equation yields negative values for any other $k$.

Proof -- Version 2

For the sake of contradiction, suppose that the icosahedron, $I$ is not the only maximal planar $5$-regular graph. Then there must be some $ G \ncong I$, that is also maximal planar and $5$-regular. Since $G$ is $5$-regular, by the Theorem 1.1.1, we know that $p=2k$ for some $k \in \mathbb{N}$ (since otherwise the sum of the degrees [ $\forall v \in V(G)$, $deg(v)$ is odd] of all vertices would not add up to an even number). Also, because $G$ is $5$-regular, $5$ edges are incident with every vertex, and each edge is shared by $2$ vertices, so $q = \frac{5p}{2} = 5k$. $G$ is maximal planar, so by the Theorem 8.1.2 \begin{equation} q=3p-6 \end{equation} \begin{equation} \Rightarrow 5k=3(2k)-6 \end{equation} \begin{equation} \Rightarrow k=6. \end{equation} Thus, for $G$ we have $p=2k=12$, $q=5k=30$, and by the Theorem 8.1.1, $r=2-p+q=2-12+30=20$. Hence, $G$ contains $20$ triangles, i.e. $G$ is the graph obtained by \emph{edge-joining}$^*$ $20$ triangles. But then $G \cong I$, which is a contradiction since we assumed the opposite. Hence we conclude that no such $G$ can exist and the icosahedron is the only maximal planar $5$-regular graph.

Q.E.D.

$^*$ Edge-joining graphs $G_1$ and $G_2$ means obtaining a new graph $G$ from the given ones in such a way, that $V(G) = V(G_1)+V(G_2)-2$, $E(G) = E(G_1)+E(G_2)-1$, and $G_1$ and $G_2$ are both proper subgraphs of $G$. So, we define edge-joining the graphs $G_i$ for $i \in \{1,\dots,n\}$ as obtaining a new graph $G$ from the given ones by edge-joining first $G_1$ and $G_2$, then the resulting graph and $G_3$, then the resulting graph and $G_4$, and so on until $G_n$.

Proof -- Version 3

For the sake of contradiction, suppose that the icosahedron, $I$ is not the only maximal planar $5$-regular graph. Then there must be some $ G \ncong I$, that is also maximal planar and $5$-regular. Clearly, if $G$ exists, it must have more vertices and edges because otherwise $G$ will be a proper subgraph of $I$, which is impossible (since no proper subgraph of $I$ is $5$-regular). But if $G$ does have more edges and vertices, then $I$ must be a proper subgraph of $G$; this means that we can obtain $G$ from $I$ by adding edges and vertices. But if we add a vertex to $I$ by connecting it to any of $I$'s vertices, the resulting graph will not be $5$-regular, and if we do not connect the new vertex to any of $I$'s vertices, the resulting graph not be connected, and therefore will not be maximal planar. Hence we conclude that no such $G$ can exist and the icosahedron is the only maximal planar $5$-regular graph.

For each version, I received comments from my professor. I am attaching the photos that include these comments.

enter image description here

enter image description here

Additionally, these might be helpful:

Problem 8.2.2 The (possibly relevant) result from this problem is that icosahedron and dodecahedron are each other's duals.

Theorem 8.1.1 (Euler's polyhedral formula)

If a plane drawing of a connected graph with $p$ vertices and $q$ edges has $r$ regions, then $p-q+r=2$.

(I am not sure how this hint can be useful and when I talked to him today he admitted that he does not know either.)

Theorem 1.1.1

Let $v_1, v_2,\dots, v_p$ be the vertices of a graph $G$, and let $d_1, d_2,\dots, d_p$ be the degrees of the vertices, respectively. Let $q$ be the number of edges of $G$. Then $d_{1}+d_{2}+\ldots+d_{p}=2 q$.

Theorem 8.1.2

If $G$ is a maximal planar graph with $p$ vertices and $q$ edges, $p \geq 3$, then $q = 3p−6$.

Theorem 8.1.8

Suppose $G$ is a maximal planar graph with $p$ vertices and $q$ edges, $p \geq 4$. Let $p_i$ denote the number of vertices of degree $i$. Then \begin{equation} 3 p_{3}+2 p_{4}+p_{5}=12+p_{7}+2 p_{8}+3 p_{9}+4 p_{10}+\ldots. \end{equation}

I think I included all of the things that can be needed, but let me know if that is not the case and I will try to clarify every point as much as I can as needed.

My question is, what do you think about those proofs? Is there any other better way to approach this problem? If so, can you give me hints? Do you think the textbook hints are correct and I should try to work on them more?

(I asked my professor about the solution he prefers, since this homework is already graded, and the problem was an extra bonus problem, but he admitted that he does not know how to solve it in a satisfying way.)

EDIT: I am sorry for such a late edit to this question. I have reviewed the answers but did not find any of them satisfactory. I will (hopefully soon) review them more thoroughly and accept one if my mind is changed.

However, the Lemma 1 of the paper @MishaLavrov has mentioned in his comment gives a very satisfactory proof of the desired statement.

$\endgroup$
3
  • $\begingroup$ I agree with your instructor that the proofs are valiant attempts, but not fully convincing. I also think that the theorem is hard to prove (if true.) I've been searching the Web for results that will help, without much success. $\endgroup$
    – saulspatz
    Dec 3 '19 at 21:05
  • 1
    $\begingroup$ I checked the statement with nauty, and it's true. The program generated $7848$ $5$-regular connected graphs with $12$ vertices, only one of which turned out to be planar. The command I used was: ./geng -c -d5 -D5 12 | ./planarg $\endgroup$
    – saulspatz
    Dec 3 '19 at 21:49
  • 2
    $\begingroup$ For an example of a proof that fully spells out the details, see Lemma 1.1 in this paper. It shows that there is a unique $3$-regular graph with faces of length $5$, but that's just the dual of this question. $\endgroup$ Dec 6 '19 at 3:33
2
+100
$\begingroup$

So here was what I came up with. I will state some lemma's without proof as they are either graph theory law at this point or simple finite computations. Note: I wrote this somewhat quickly and don't really feel like editing it into better shape. It is lacking some finesse but I think it is a nice proof.

Lemma 1. Every planar graph on $n$ vertices has at most $3n-6$ edges.

Lemma 2. Every maximal planar graph on $n$ vertices has $3n-6$ edges and has a planar triangulation.

Lemma 3. A 5-regular maximal planar graph has exactly 12 vertices.

Proof: Let $G$ be a 5-regular maximal planar graph. As a 5-regular graph has $\frac{5n}{2}$ edges, $n$ is even. It follows from Lemma 1 that $G$ must have $\frac{5n}{2} \leq 3n-6$ edges. Thus $n \geq 12$.

Similarly, as $G$ is maximal planar it has exactly $3n-6$ edges and thus $n = 12$. This ends the proof.

Lemma A. Every edge of $G$ is in exactly 2 triangles.

Proof: First suppose that there exists an edge of $G$ that is in at most 1 triangle of $G$. As the faces of a planar graph are separated by the edges and each face is a triangle, this is a contradiction.

Now suppose that there is an edge in at least 3 triangles. We may assume some edge $e$ is in exactly 3 triangles. Consider the vertices $x,y,z$ incident with the edge $e$ and suppose that $x$ and $y$ have been embedded in the plane. It follows from the planarity of $G$ that $z$ must be embedded such that $z$ is entirely contained in one of the existing faces surrounding $e$. As this face is a triangle, $z$ has degree 3 which is a contradiction. This completes the proof.

Lemma 4. For every vertex $u$ there exists a vertex $v$ such that $N(u)$ is vertex disjoint from $N(v)$.

Proof: For every vertex $v$, $G[N(v)]$ is a 5-cycle as $G$ has a planar triangulation. Moreover two adjacent vertices in $N(v)$ have a single common neighbour in $G-v$ by Lemma A. It follows that the size of the second neighbourhood of $v$ is 5. Therefore there exists a vertex $u$ such that $N(u)\cap N(v) = \emptyset$. This ends the proof.

Theorem: The only 5-regular maximal planar graph is the icosahedron.

Proof: Let $G$ be a 5-regular maximal planar graph. By Lemma 3, $G$ has 12 vertices. Let $u$ and $v$ be two vertices of $G$ with $N(u) \cap N(v)$, by Lemma 4. As $G$ is a planar triangulation both $G[N(u)\cup u]$ and $G[N(v)\cup v]$ have 10 edges and each vertex of the neighbourhoods has degree 3. Adding edges between the neighbourhoods such that each edge of the cycles lies in exactly one triangle gives an icosahedron. This ends the proof.

Edit Note: The reason this answers the "only" question is that it shows constructively that the only graph able to be constructed is the icosahedron. Effectively it reduces the problem to placing the 10 final edges. But the maximal planar property forces those edges.

Edit 2 Introduced Lemma A to fix the hand waving of Lemma 4. Also fixed Lemma 4, it had the right idea but was badly written.

$\endgroup$
7
  • $\begingroup$ This seems alright. But, isn’t Lemma 1 unnecessary? It seems as if you can simply use Lemma 2 directly. $\endgroup$
    – ViHdzP
    Dec 11 '19 at 7:31
  • $\begingroup$ Yeah absolutely. I wrote this as a stream of consciousness. That may be why some things seem out of place. $\endgroup$ Dec 11 '19 at 7:33
  • $\begingroup$ Seems similar to one of the proofs I wore above, in the question statement... $\endgroup$ Dec 11 '19 at 17:34
  • $\begingroup$ No. I construct the graph where as you run out of "room for extra consideration" ... What ever that means. The number of triangles and number of vertices alone does not give you the global structure of the graph. This is what your professors comments are saying. Without being too harsh, all of your proofs are wrong and assume false statements like "there is at not one maximal planar graphs with a given number of vertices'. The choice of two vertices to stitch together is the key part of the proof, not some side show. $\endgroup$ Dec 11 '19 at 21:17
  • $\begingroup$ I don't understand Lemma 4. Why can't two adjacent vertices have two common neighbors? $\endgroup$
    – saulspatz
    Dec 12 '19 at 21:39
1
$\begingroup$

This is an extended comment. I plan to post a bounty on this problem, so I'm posting my ideas on it.

EDIT It seems that the question is not yet eligible for a bounty. I'll post a bounty one as soon as I can.

The OP has demonstrated that a $5$-regular maximal planar graph has $12$ vertices. It seems there are various ways of demonstrating that such a graph is hamiltonian. For example, there is a theorem of Jackson (cited in https://arxiv.org/pdf/1204.6457.pdf) that a $2$-connected $k$-regular graph on at most $3k$ vertices is hamiltonian. (I don't know much at all about hamiltonian graphs, and there may well be a way to prove this without using such an advanced theorem.)

So, my idea was to show that there is essentially only one way for the conflict graph to be bipartite, so that the graph is planar. Here is a drawing of the icosahedron graph.

enter image description here

The Hamilton cycle forms the outer dodecagon, and the remaining edges are diagonals. The conflict graph is the graph whose vertices are the diagonals, with two vertices adjacent iff they intersect in the interior of the dodecagon. The colors show that the conflict graph is bipartite, and hence the graph is planar. (We can redraw all the red edges as arcs exterior to the dodecagon, with no intersections.)

By Tutte's theorem on conflict graphs, the graph is planar if and only if the conflict graph is bipartite, so we need to show that there is essentially only one way to construct a bipartite conflict graph. We must show that there have to be $9$ vertices in each part, and there is essentially only one way to draw the diagonals.

The label on a vertex of the dodecagon indicate the number of black and red diagonals, respectively, incident on that vertex. It will be observed that the cyclic sequence of the red numbers is the reverse of the cyclic sequence of the black numbers. Since the sum of the numbers at each vertex must be $3$, it is likely that if we could prove that the sequence of black numbers is unique, we could prove that the two sequences must be related in the way shown.

However, I don't have a good idea how to prove any of this. My instinct is to write a computer program to exhaustively test all possibilities. I've already confirmed the theorem with nauty, as I mentioned in a comment, so this doesn't seem like much of an advance.

EDIT

This idea doesn't work, at least not in the simple form I'd hoped for. It's easy to find $9$ non-intersecting diagonals with the sequence $1,0,2,2,2,2,1,0,2,2,2,2$ so apparently, even if we can prove that both parts must have $9$ vertices, we have to show that there is only one way to choose compatible red and black sequences. Even after doing that, we have to show that the red and black sequences determine the graph, which may or may not be true. The conflict graph depends on the particular embedding of the graph in the plane, so it seems possible that there would be non-isomorphic conflict graphs.

It doesn't seem like my idea is very useful, but I'll leave this up in case it gives someone else a good idea.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.