0
$\begingroup$

Can anyone please walk me through how to solve problems like this?

1) how many diagonals does an n-gon have?

2) can a kindgom in which 77 roads lead out of each city, have exactly 10000 roads?

1 Answers 1

2

(1) There is a bijection between diagonals and pairs of non-adjacent vertices of the $n$-gon. There are $\binom{n}2$ pairs of vertices altogether, of which $n$ pairs consist of adjacent vertices, so there are $\binom{n}2-n$ pairs of non-adjacent vertices the same number of diagonals. If you want, you can expand this to get rid of the binomial coefficient:

$\binom{n}2-n=\frac{n(n-1)}2-n=\frac{n^2-n}2-n=\frac{n^2-3n}2=\frac{n(n-3)}2$

(and you can pick your favorite form).

(2) In graph-theoretic terms this is asking whether a graph in which every vertex has degree $77$ can have exactly $10000$ edges. Each edge has two ends, so the sum of the degrees of the vertices in any graph is twice the number of edges. If our kingdom has $n$ cities (and our graph therefore $n$ vertices), the sum of the degrees will be $77n$. If there were $10000$ roads (edges), we’d have $77n=2\cdot10000$; is this actually possible?

  • 0
    @Ross: It’s all the same mod $2$! Thanks to you and Cameron.2012-11-05