There is a square, denoted by points A, B, C, and D. There are 30 distinct points located inside the square (call these $A_2, A_3, A_4, ... A_{31}$.

Non-intersecting segments $A_iA_j$ vertices are drawn for various pairs (i, j) with $1\le i,j\le 34$, such that the square is dissected into triangles. Assume each $A_i$ is an endpoint of at least one of the drawn segments. How many triangles are formed?

How would this look like in a diagram? How would I solve this problem?


We begin with Euler's formula: $v-e+f=2$. We know there are $v=34$ vertices.

We can find another formula by counting the number of face-edge pairs in two different ways: by considering (a) for each face, the number of boundary edges, and (b) for each edge, the number of neighboring faces.

The external face is bordered by $4$ edges and every other face is bordered by $3$ edges. Every edge borders $2$ distinct faces. Hence there are $2e=3(f-1)+4$ face-edge pairs in the graph.

We solve this system of linear equations to find $f$, and hence there are $f-1$ triangles.


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.