What polyhedron has 11 vertices and 17 edges

Question

On my math test it asked me how many polygons it takes to create a polyhedron that has $11$ vertices and $17$ edges. I'd just like to see what the shape would look like and I can figure out the polygon part myself.

Answer 1

Hint: Euler's Formula states that if a polyhedron has $V$ vertices, $E$ edges, and $F$ faces, then $V-E+F = 2$. This tells you how many faces the polyhedron has.

Answer 2

OK.. imagine a pentagonal prism. Now remove one of the (rectangular) side faces, and create a vertex in the middle of each of the side edges next to that gap. Now pull those two new vertices together, extending the side faces into pentagons also. Finally fill the gap above and below the new vertex with two triangles.

---

In one of those classic shifts of perception, Henry recognized that essentially the same shape as shown in my image above could also be achieved from a cube with two adjacent corners sliced off so as to reduce one edge of the cube to a single remaining vertex.

Answer 3

Another hint: a polyhedron is a planar graph, so draw 11 vertices in some arrangement, and try to draw 17 non-intersecting lines joining these vertices in a way that divides the plane into $F$ regions, where $F$ is the value you obtained from JimmyK4542's hint. Note that the region comprising of the entire area "outside" of the graph counts as one of the faces! Once you have done this, you can easily characterize the types of faces such a polyhedron has, and their relation to each other.

I should also mention that such a polyhedron is not unique in the sense that there exists more than one such planar graph; however, the number of faces is necessarily the same in all cases.

Answer 4

This is to address the part of question "what the shape would look like". If one only want to know the number of faces for such a shape, look at JimmyK4542's answer instead.

It turns out there are many polyhedra with $11$ vertices and $17$ edges. Even when we limit to convex polyhedra, there are $38$ topological distinct choices! The key of counting start from following little observation:

$$2 \times 17 - 3\times 11 = 1\tag{*1}$$

The shape has $17$ edges. Since each edge contributes $2$ end points, there are $34$ end points. Since the degree of any vertex is at least $3$, any shape with $11$ vertices has at least $33$ end points. $(*1)$ implies among the $11$ vertices, one of them is distinguished and has degree $4$ while the remaining $10$ vertices have degree $3$.

If we remove the distinguished vertex and the 4 edges/4 faces attached to it, the boundary of what's remain on the surface will be a circle. You can think of it as cyclic graph with $4$ vertices.

To generate a list of possible shapes, we can start adding vertices of degree $3$ to this cyclic graph. When we add a vertex to this cyclic graph, each will contribute one free end point. We can join the free end points from two vertices on the cyclic graph. We can also add some "external" vertices to deal with the dangling end points.

It turns out not all graphs constructed in this manner corresponds to a convex polyhedron.
To filter out the graphs which does, we need two concepts:

• $k$-vertex connected - a graph $G$ is said to $k$-vertex connected (or $k$-connectged) if it has more than $k$ vertices and remains connected whenever fewer than $k$ vertices are removed.
• planar graph - a planer graph is a graph that can be embedded in the plane.

In terms of these concepts, we can use following theorem to filter the graphs:

Steinitz's theorem - The edge graph of any convex polyhedron is a 3-connected planar simple graph. Every 3-connected planar simple graph can be realized as the edge graph of a convex polyhedron.

After the filtering, there are $38$ graphs remain. Following is a picture showing the $1$-skeleton of the possible shapes after one removed the distinguished vertex and the $4$ edges attached to it.

This $38$ choices fall into $4$ groups according to the number of vertices $N_i$ added to the ancestral cyclic graph.

$$\begin{array}{rr} \verb/top-left/ & 10 \text{ shapes for } N_i = 6\\ \verb/bottom-left/ & 13 \text{ shapes for } N_i = 5\\ \verb/top-right/ & 12 \text{ shapes for } N_i = 4\\ \verb/bottom-right/ & 3 \text{ shapes for } N_i = 3 \end{array}$$

Given any one of these $38$ graphs, one can use it to construct the corresponding convex polyhedron. For the few graphs I have played with, one can start with a square pyramid, draw a few guidelines on the square base according to the graph. "chop off" some vertices or "smooth out" some edges according to the guidelines.

Let's look at some examples.

• In graph $1a$, it tell us to first "chop off" a vertex on the base and then "smooth out" one of the generated edges twice. This is what you get.

• In graph $1b$, it tell us to pick a pair of opposite edges from the base, "smooth out" one of them once and the other one twice. What you get is something completely different than the first example.

  

Among the remaining graphs, there are other interesting shapes. I will just leave their visualization for those who love to exercise their imagination.