Questions

1. At a party of $n$ people there are some people who initially don't know each other and some who do. It turns out that there are either three people who didn't know each other or three people who did. What's more if $n$ had been any smaller this couldn't have happened. What is $n$?
2. In a group of nine people, one person knows two of the others, two people know each other, four each know five others, and the remaining two each Kknow six others. Show that there are three people who all know each other.
3. A man and his wife gave a formal party for four of their married friends. Various friends shook hands as they were introduced and naturally they didn't shake hands with their partners or more than once with the same person. Over drinks, the man asked everybody how many times they had shaken hands and discovered that no two people had shaken hands the same number of times. His wife then told him how many times he had shaken hands. What did the wife say?

Questions

1. A labelled graph is a graph where the `names' of the vertices are important. For instance on flight maps it's important to know whether the edges joining two vertices is between the vertices Melbourne and Sydney or Brisbane and Adelaide. How many labelled graphs are there on $n$ vertices?
2. Students, in a small class of 6, have to wait outside the maths class door in single file before their teacher lets them in. So that they get to know each other he tells them that they can't stand next to two classmates (in front or behind) more than once. How many classes go by before the teacher's condition is violated?
3. Twenty football teams take part in a tournament. On the first day all the teams play one match. On the second day all the teams play a further match. Prove that after the second day it is possible to select 10 teams, so that no two of them have yet played each other.