# Lazy caterer's sequence, cutting pizza into most pieces with n straight cuts. Graph theory proof.

is there a way to solve this problem using graph theory? I used Euler's formula to find that when you use the method in which every new line intersects the old line in different places gives you $\frac{(n-1)n}{2}+1.$

proof.

Make make the intersections of line segments the vertices and the parts of these line segments joining the vertices the edges.

The number of times any line intersects is $n-1$ (without counting the two times it intersects the circle). Therefore the number of vertices is V=$\frac{(n-1)*n}{2}+2n=\frac{(n+3)(n)}{2}$ since each inner vertex is counted twice and each line intersects the circle twice.

each line segment is partitioned into n line segments and the circle is partitioned into $2n$ edges.

$E=n(n+2)$

using Euler's formula we know $\frac{(n+3)(n)}{2}+F-n(n-2)=2$

therefore $F=n(n-2)- \frac{(n+3)(n)}{2}+2$ so $F=\frac{n(n-1)}{2}+2$

however we counted the outside face also so without that face:

the pizza is cut into $\frac{n(n-1)}{2}+1$ faces as desired.

Is there a way to use this to prove this is the greatest value of F for a fixed n?

-
I found this, I can't read it though jstor.org/discover/10.2307/… –  dREaM Mar 19 '13 at 23:09