# The Average Degree of Theta Graphs

Pat Morin

I will describe research that started when Sander Verdonschot told me
that, in his experiments on random point sets, the θ_{6}
graph had 25% more edges than the θ_{5} graph. Intuition
suggests that θ_{6} should have 6/5-1=20% more edges.

In order to understand this discrepancy we derive exact bounds
on *d*_{k}, the average degree of a vertex in the
θ_{k} graph of points that obey a Poisson
distribution over R^{2}. We then show that this result carries
over (with small error terms) to a set of *n* points uniformly
distributed in a square, so that the expected number of edges in
such a graph is ½*d*_{k}n±*o*(*n*).
We also show that, in the same setting, the number of edges in the
θ_{k} graph is highly concentrated around its
expected value.