\section*{Problem 3}

A graph has 30 points and each point has 6 edges. Find the total number of triples such that each pair of points is joined or each pair of points is not joined.

\section*{Answer}

1990


\section*{Solution}

There are 30. 29. \(28 / 6=4060\) triples in all. Let \(\mathrm{m}\) be the number of triples with 0 or 3 edges, and let \(n\) be the number of triples with 1 or 2 edges. So \(m+n=4060\). Each point is joined to 6 others, so it is in \(6 \cdot 5 / 2=15\) triples where it is joined to both the other points, and it is in 23. \(22 / 2=253\) triples where it is not joined to either of the other points. So the total number of triples \((\mathrm{a}, \mathrm{b}, \mathrm{c})\), where \(\mathrm{a}\) is joined to \(\mathrm{b}\) and \(\mathrm{c}\) or not joined to \(\mathrm{b}\) or \(\mathrm{c}\) is \(30(15+253)=8040\). This counts the \(m\) triples 3 times each, and the \(n\) triples once each, so \(3 m+n=8040\). Hence \(m=\) 1990.

