# Combinatorics

• Dec 2nd 2008, 11:37 AM
Carrick
Combinatorics
An octagon has 8 sides. How many diagonals does an octagon have?

Little confused with this question. . can anyone help?

Thanks
• Dec 2nd 2008, 11:56 AM
vincisonfire
Let's take one vertex. It can be linked to 7 other vertices.
Let's take the next vertex. It can also be linked to 7 other vertices but there is one diagonal that is already drawn. Therefore, there is 6 new diagonals.
...
$\sum_{i=1}^7 i = \frac{i(i+1)}{2} = 28$*
• Dec 2nd 2008, 12:37 PM
Plato
Quote:

Originally Posted by vincisonfire
Let's take one vertex. It can be linked to 7 other vertices.
Let's take the next vertex. It can also be linked to 7 other vertices but there is one diagonal that is already drawn. Therefore, there is 6 new diagonals. $\sum_{i=1}^7 i = \frac{i(i+1)}{2} = 28$*

Unfortunately, the answer given above is an over count.
The answer is 20. An octagon is a subgraph of complete graph, $K_8$ on eight vertices. $K_8$ has 28 edges but only 20 are diagonals of the octagon.
In general, for an n sided figure there are ${n \choose 2}-n = \frac {n(n-1)}{2}-n = \frac {n(n-3)}{2}$ diagonals.
• Dec 2nd 2008, 12:45 PM
vincisonfire
My apologies. Counting sides for diagonals (Headbang)
• Dec 2nd 2008, 02:27 PM
Plato
Quote:

Originally Posted by Carrick
What did it mean by diagonals? I'm doing simple combinations right now, your theory seems a little heavy

The above quote is from a PM: please ask such questions in the open. Others may also benefit from the answer.

An octagon is a figure with eight vertices and eight edges. If two edges share a vertex, then the edges are said to be adjacent. But any two vertices will determine a line segment. If you join each vertex with each other vertex we have what is known as a complete graph. In the case of eight vertices the complete graph, $K_8$, has 28 edges. The diagonals are the edges that are in the original octagon. Thus 20 are diagonals.

Thus in $K_n\;,\;n\ge 3$ there are ${n \choose 2} = \frac {n(n-1)}{2}$ edges.
But n of the edges are not diagonals.