Counting Diagonals of a Polyhedron

(An archive question of the week)

In gathering information on how to count the diagonals of a polygon, I found this long discussion about a similar-sounding issue, which is hardly more difficult, yet far more complex. It was interesting to explore what the question means, and take it in different directions, on the way to the sort-of-simple answer.

Diagonals of polygons and polyhedra

Here’s the question, from 1999:

Diagonals in 3D Figures

I am having great difficulty with math and require assistance. Could you help? I have the formula n(n-3)/2, but I don't know how to justify or prove it. Another thing is, could you please tell me the number of diagonals in various 3D shapes, such as a tetrahedron, cube and so on. Is there a formula for this or is it just coincidental?

I first explained the polygon formula, as we’ve seen it before:

Hi, Jamie.

Let's think how we can count the diagonals in a polygon. Pick any 
vertex; there are N ways to do that. Now pick any vertex to go to 
EXCEPT the two neighbors (and the point itself, of course). How many 
ways are there to do that? When you finish, you'll have counted every 
diagonal - except that you will have counted each one twice, once 
starting from each end. Taking that into account will give you the 
formula.

Can we extend this from two-dimensional polygons to three-dimensional polyhedra? I suggested an approach that leads to a final formula we’ll end up with:

Now, for a general polyhedron, the same method would work except for one detail: there can be any number of "neighbors" to any vertex. But you can use a similar method to find the TOTAL number of segments that can be drawn between any two vertices; then you can just subtract from your count the number of edges in the polyhedron. Since you can make different polyhedra with the same number of vertices but different numbers of edges, you can't give an answer based only on the number of vertices.

Have you looked at a tetrahedron and tried to count the diagonals? Try it - you'll find there aren't any. For a cube, there will be two on each of the six faces, and three going through the center. See if that agrees with the formula you come up with.

Jamie replied with a few (incorrect) manually counted numbers, showing that he was not yet ready to derive a general formula:

Could you please help me? In a 3D object, the tetrahedron has 0 diagonals, the cube has 15 and then the pentagonal prism has either 28 or 32. Can you tell me the next 3 or 4 terms so that I can work out the sequence? Thank you very much.

As we saw last week, we can think of the number of diagonals of a polygon as a sequence, indexed by the number of sides, n: for n = 3, 4, 5, …, we have d = 0, 2, 5, …, from which you could guess the formula, or (far better) see a pattern and why it occurs. That is what Jamie was hoping for here. Unfortunately, an approach starting from specific numbers will not work, even if they are right.

I answered:

There are a couple of problems in trying to figure this out by making a list. For one thing, there really is no "sequence": you can't put all the possible polyhedra in an ordered list as you can with polygons, because there are lots of different ways to connect N vertices to make a shape. Secondly, even if you can see a pattern in the jumble of shapes you consider, it will be hard to be sure it's a real pattern if you haven't given thought to the reason for the pattern. It's much easier to find patterns if you look for a pattern in the way you count, rather than just make a list of numbers and then look for a pattern there.

We’ll see some examples below to demonstrate that we can’t just put polyhedra in a row with n = 3, 4, 5, … . But trying things out for small cases is still valuable:

Yet it will be worthwhile for you to make a list of shapes and try to count the edges and the diagonals of each, in order to get to know them. You'll want to get a feel for how diagonals work, so it wouldn't be helpful for me to just give you a list - you need to do some counting on your own. But I'll start your list to give you some ideas on what to look for and how to count the diagonals.

Some examples

I started with an example of each of several types of polyhedra, because each type has its own patterns.

Let's list several characteristics of each shape: the number of Vertices (V), Edges (E), Faces (F), and Diagonals (D).

Tetrahedron
                        V   E   F   D
                       --- --- --- ---
                        4   6   4   0
             +
            / \\
           /   \ \
          /     \  \
         /       \   \
        /       __\__ +
       /____----   \ /
      +-------------+

Since every point is connected to every other point, there's nothing left to be a diagonal.

Square pyramid
                        V   E   F   D
                       --- --- --- ---
                        5   8   5   2
            +
           / \\
          /   \ \
         /     \  \
        /       \   \
       /---------\---+
      /           \ /
     +-------------+

The top point is connected to all the others, so the only diagonals are the two in the base.

Triangular hexahedron
(Twin tetrahedra)
                        V   E   F   D
                       --- --- --- ---
                        5   9   6   1
             +
            / \\
           /   \ \
          /     \  \
         /       \   \
        /       __\__ +
       /____----   \ /
      +-------------+
       \           /
        \         /
         \       /
          \     /
           \   /
            \ /
             +

The top and bottom points are connected to everything but each other; the "equatorial" points are connected to everything, leaving only the one diagonal.

Notice that these last two polyhedra have the same number of vertices, but different numbers of edges. But the sum of the number of edges and the number of diagonals is the same for both, because that's just the total number of lines you can draw connecting any two points.

This is our first demonstration that V is not enough. I also hinted again towards our ultimate answer.

Continuing, with six vertices:

Octahedron
                        V   E   F   D
                       --- --- --- ---
                        6  12   8   3
            +
           / \\
          /   \ \
         /     \  \
        /       \   \
       /---------\---+
      / \         \ /
     +-------------+
       \  \      //
         \ \    /
           \\  /
             +

Each point is connected to every point except the opposite vertex; the three pairs of opposites form three diagonals.

Pentagonal pyramid
                        V   E   F   D
                       --- --- --- ---
                        6  10   6   5
              +
             /|\
            /|||\
           / ||| \
          / | | | \
         /  | | |  \
        /  |  |  |  \
       /___|_-+-_|__ \
      +-  |       |  -+
       \  |       |  /
        \|         |/
         +---------+

The top point is connected to all the others, so the only diagonals are the five in the base.

Triangular prism
                        V   E   F   D
                       --- --- --- ---
                        6   9   5   6

                     +
                /    |\
          /          | \
     +------------------+
     |               |  |
     |               |  |
     |               |  |
     |               |  |
     |               +  |
     |          /     \ |
     |    /            \|
     +------------------+

The diagonals are all in the three sides.

I've given you three different polyhedra with six vertices. It gets a lot worse with more vertices!

Here are better pictures of the six examples, including the diagonals:

Again, I didn’t do this to generate numbers from which Jamie could deduce a formula, but (a) to demonstrate that polyhedra don’t form a sequence; (b) to show that the number of diagonals is not a function of V alone; and (c) to give some sense of what diagonals really are.

In particular, you might notice that the second, fifth, and sixth have only “face diagonals” lying on the “skin”, while the third and fourth have only “body diagonals“, diving through the middle of the “body”. Others, as we’ll see in a moment, have some of each.

I'm not sure why you gave two numbers for the pentagonal prism; the correct count, according to my formula, is 30: 5 in each base, 2 in each of 5 sides, and 2 reaching from each vertex on one base to vertices on the other base through the interior.

The important thing to see is that you can't just look at V and tell me what D will be. You need to know at least two things about the shape. There is a formula that relates D+E to V, which is what I suggested to you in my last response; and another that relates V+F to E. Putting these together, it turns out that D+F is determined by V. So if you know V and either E or F, you can figure out what D is.

Here are Jamie’s cube (square prism) and pentagonal prism:

I neglected to point out that Jamie missed one diagonal for the cube; there are 2 face diagonals for each of 6 faces, and 4 body diagonals (to the opposite vertex), for a total of 12 + 4 = 16.

We’ll get to the final formula I mentioned eventually, but I’ll mention here the two that we’ll be using. The first is simple: $$V = D+E$$ because every line from one vertex to another is either an edge or a diagonal, and it can’t be both.

The second was discussed in More on Faces, Edges, and Vertices: The Euler Polyhedral Formula: $$ V-E+F=2$$

Jamie wrote back:

Thank you very much for your help, it is greatly appreciated, I now understand more fully what my task actually is. Thank you once again for all your time with me.

Formulas

But he hadn’t stopped thinking! Three days later, he wrote again:

Thank you for your faith in me, this is just a check, I have found your information on pyramids useful, and have come up with the formula 

         (n-1)(n-4)
     d = ----------
             2

Is this correct? Just one other query; is there a link between the formula for pyramids and prisms, or is there one formula linking all 3D shapes together?

I answered:

Yes, you have the right formula for a pyramid. I'm not sure how you found it, but there's a very easy way: all the diagonals will be in the base, since the apex is already connected to all other vertices; so you just have to put n-1 into the formula for diagonals of a polygon.

You can do something similar for a prism: many of the diagonals will be in one or the other of the bases, and the rest can be easily counted because they go from a vertex on the top to a vertex on the bottom. I'm not sure there would be a direct link to the pyramid formula, but they certainly aren't unrelated either.

To be specific, the formula for a pyramid, using \(d=\frac{1}{2}n(n-3)\) for a polygon with n vertices, is (taking v as the total number of vertices) $$d=\frac{(v-1)((v-1)-3)}{2}=\frac{(v-1)(v-4)}{2}$$ as Jamie said. The formula for a prism (taking v as the total number of vertices, so that the number of vertices in each base is b = v/2) is $$d=2\cdot\frac{b(b-3)}{2}+b(b-1)=2b^2-4b=2b(b-2)=\frac{v(v-4)}{2}$$ These can be checked against my examples.

I had been hinting at the more general formula for some time, and did so again:

There is a very simple general formula for the total number of lines that can be drawn between any two of a set of n points in space, and this will be the sum of the number of edges of the polyhedron and the number of diagonals. You can easily derive your formula for a pyramid, or the one for a prism, from this by coming up with a formula for the number of edges. For example, for a pyramid, the number of edges is just 2(n-1), since there are n-1 edges in the base, and the same number of edges from the base to the apex.

We’ll get there!

Over the next few weeks, we discussed the derivation of the formula for prisms; Jamie had little knowledge of algebra yet, so there were a lot of details to go over, all of which I will omit here.

Regular polyhedra, regular graphs

Then Jamie moved on to another specific case:

This is my last query; then I've figured the whole thing out. Can you tell me how many diagonals there are in a dodecahedron and an icosahedron?  Or can you tell me where on the Internet I can find that answer?

I answered:

It's time to introduce you to a different approach to the prism, which you can apply to these regular polyhedra.

Regularity means that some or all features of a shape are true everywhere. A prism is not a regular polyhedron, because not all faces are the same shape and not all edges are the same length, and so on; but it is regular in one way: at every vertex you find the same number of edges, namely two going to adjacent vertices in the same base, and one going to the corresponding vertex in the other base. Luckily, that's the kind of regularity that helps most with this problem.

You can use this to do the same thing you did originally in counting the diagonals of a polygon. If there are v vertices in all, you can pick any of them to start a diagonal, and then you go from there to any vertex except itself and the three other vertices to which it is connected, giving you (v-4) choices for each of the (v) starting vertices. Since you will have counted each vertex twice this way, the total number of diagonals is

         v(v-4)
     D = ------
           2

Sound familiar?

You can use the same method for any regular polyhedron. See what you get! (You'll find that regular polyhedra are pretty boring.) Then see if you can actually visualize where these diagonals are and see that you counted them correctly.

In graph theory, the number of edges at a vertex is called its degree; when all vertices have the same degree, the graph is regular. So prisms and regular polyhedra have regular graphs.

Jamie applied these ideas to the two regular polyhedra he’d asked about (unfortunately getting some numbers wrong again):

Thank you for the e-mails. I find that I now understand it all, except for two small areas, which I hope you can help me with. The first is: using the prism formula and the notes you gave me, I worked out the number of diagonals. Can you check my data, see if they are correct, as I have two conflicting sources, the Internet and also an encyclopedia:

               Vertices   Edges   Faces   Diagonals
Dodecahedron      12       30      12         48
Icosahedron       20       30      20        160

If those are correct, which I believe them to be, I have come up with this logic, please tell me if I'm right.

     v(v-j)
     ------
       2

1. v  This represents the total number of vertices in the polyhedron

2. v-j  The total number of vertices minus j, where j is equal to the number of diagonals unable to be drawn to from any given starting vertex. For instance in the cube, from any given vertex, you are unable to draw diagonals to 3 vertices as they are connected with edges. Then you can't draw a diagonal to the vertex from where you started. So it would be the total number of vertices minus 4. This value would be (for all except two polyhedra) the shape of which the polyhedron is made from plus 1. The exceptions are the cube, where the 1 need not be added; and the octahedron, where it is needs to be added to 2.

3. 2  It is placed over two because by using this method you count each diagonal twice.

The dodecahedron, like the prism, has vertices of degree 3, so Jamie’s “j” is again 4; but there are 20, not 12, vertices, so we get $$d = \frac{v(v-j)}{2} = \frac{20(20-4)}{2} = 160$$ The icosahedron has 5 edges at each vertex, so “j” is 6; it has 12, not 20, vertices, so we get $$d = \frac{v(v-j)}{2} = \frac{12(12-6)}{2} = 36$$

I replied, neglecting to point out the errors in the numbers, and focusing on the thinking:

This sounds fine except for the details of how you find j. I would express the formula not in terms of j, which is not an obvious number, but in terms of something like the number of edges that meet at each vertex. It has nothing to do with the shape of the faces. You might like to make a chart for all the regular polyhedra and a few prisms, showing not only V, E, and F, but also the number of edges per face and the number of edges per vertex. Then show what your "j" is, and see how it's related. Or just think carefully about what it means to be unable to draw a diagonal to a vertex.

Jamie’s ideas about calculating “j” appear to be based on the guess that it would be related to the shapes of the faces, and trying to find a relation between the numbers, rather than looking behind the numbers for a real reason. This is all too common when students have been taught to guess at patterns rather than derive formulas from processes, as we discussed here.

General formulas

We never got to the end I was aiming for, because Jamie was too new to both algebra and geometry to be ready to see past the particulars. Let’s first finish what I suggested above, and then look more generally.

First, we can finish the formula for polygons in which each vertex has the same number of edges (regular graphs). If we call the degree of each vertex g, then Jamie’s “j” is just \(g+1\), and his formula becomes $$d = \frac{v(v-g-1)}{2}$$

Or, since the total number of “edge-ends” can be calculated as either \(2e\) or as \(vg\), we find that \(g = \frac{2e}{v}\), and the formula becomes $$d = \frac{v(v-\frac{2e}{v}-1)}{2} = \frac{v^2-v-2e}{2}$$ Checking this for our pentagonal prism with \(v=10\) and \(e=15\), we get $$d = \frac{10^2-10-2(15)}{2} = 30$$

If the graph of a polyhedron is not regular, then the best we can do is to use the idea I’ve mentioned since the start, that the diagonals consist of all segments between vertices, minus those that are edges: $$d = {v\choose 2}-e = \frac{v(v-1)}{2}- \frac{2e}{2} = \frac{v^2-v-2e}{2}$$

Amazingly, we get the same formula whether or not we assume the vertices are regular! This universal formula can also be written as $$d = \frac{v(v-1)}{2} – e$$

Since edges are often harder to count than faces and vertices, let’s use only the latter in a formula. Knowing that \(v-e+f=2\), we can replace e with \(v+f-2\). That yields this formula: $$d = \frac{v^2-v-2(v+f-2)}{2} = \frac{v^2-3v-2f+4}{2} = \frac{v(v-3)}{2}-f+2$$

From this, we can re-derive our previous formulas for prisms and pyramids:

Prism

There are 2 bases and v/2 sides, so that \(f  = \frac{v}{2}+2 = \frac{v+4}{2}\); therefore, $$d = \frac{v(v-3)}{2}-\frac{v+4}{2}+2 = \frac{v^2-3v-v-4+4}{2} = \frac{v^2-4v}{2} = \frac{v(v-4)}{2}$$

Pyramid

There is 1 base with v – 1 sides, so that \(f  = v\); therefore, $$d = \frac{v(v-3)}{2}-v+2 = \frac{v^2-3v-2v+4}{2} = \frac{v^2-5v+4}{2} = \frac{(v-1)(v-4)}{2}$$

It’s more natural to discuss these in terms of the number of sides in the base:

n-gonal prism

Since \(v = 2n\), we get $$d = \frac{v(v-4)}{2} = \frac{2n(2n-4)}{2} = 2n(n-2)$$

n-gonal pyramid

Since \(v = n+1\), we get $$d = \frac{(v-1)(v-4)}{2} = \frac{n(n+1-4)}{2} = n(n-3)$$

Regular polyhedra

To check the formulas above, we can calculate these specific forms:

Tetrahedron: 3-gonal pyramid, $$d = n(n-3) = (3)(3-3) = 0$$

Cube: 4-gonal prism, $$d = 2n(n-2) = 2(4)(4-2) = 16$$

Octahedron: v = 6, f = 8, so $$d = \frac{6(6-3)}{2}-8+2 = 9-8+2 = 3$$

Dodecahedron: v = 20, f = 12, so $$d = \frac{20(20-3)}{2}-12+2 = 170-12+2 = 160$$

Icosahedron: v = 12, f = 20, so $$d = \frac{12(12-3)}{2}-20+2 = 54-20+2 = 36$$

These agree with our previous counts.

Leave a Comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.