Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This problem came from a Putnam problem solving seminar.

If each person in a group of n people is a friend of at least half the people in the group, then show that it is possible to seat the n people in a circle so that everyone sits next to friends only.

My idea was to use induction on $n$; if $n$ is odd we can remove a person, note that the remaining $n-1$ people all have at least $n/2$ friends left, use our inductive hypothesis to seat them, and then use the pigeonhole principle to seat the last person.

Unfortunately, this doesn't work when $n$ is even because after removing a person, some of the remaining people might have less than $n/2$ friends left. In fact, my friend who actually participated in the seminar said they had the same issue, but didn't address it because they ran out of time.

Is this sort of induction a reasonable approach? If so, how would we deal with the case when $n$ is even? If not, what's a better way to think about the problem?

P.S. I'm not sure of the best tags for this question, so please feel free to re-tag if necessary.

share|improve this question

2 Answers 2

up vote 11 down vote accepted

This is known as Dirac's theorem. I don't know if an inductive proof is possible; the standard proof is extremal. You consider the longest sequence of friends and show by contradiction that it must be a Hamiltonian circuit. I can edit with more details if you want the full argument; it's quite nice.

Edit: the argument is as follows. It can be found, for example, in Bollobas' Modern Graph Theory (p. 106). First let's establish the graph-theoretic language. Let $G$ be a graph on $n$ vertices, $n \ge 3$. For each $v \in G$ let $d_v$ denote the number of neighbors of $v$. Then the claim is that if $d_v \ge \frac{n}{2}$ for each $v \in G$, then $G$ is Hamiltonian.

We claim that $G$ is connected. Indeed, if $v, w \in G$ then $v$ and $w$ each have $\frac{n}{2}$ neighbors out of a possible $n-1$, so they must share some neighbor. (This step works under the weaker assumption that $d_v + d_w \ge n$ for each $v \neq w$.)

Now suppose that $G$ is not Hamiltonian. Let $v_1, ... v_k$ be a path all of whose vertices are distinct with $k$ maximal. Then $v_1$ and $v_k$ have no neighbors outside the path (by maximality), so all of their neighbors must be one of $v_1, ... v_k$. In addition, $v_1$ cannot be connected to $v_k$; otherwise we would have a cycle of length $k$, and by connectivity this cycle would be connected to some $w$ not in the cycle, giving a path of length $k+1$, which contradicts maximality.

More generally, $v_1$ cannot be connected to a vertex $v_{i+1}$ with the property that $v_i$ is connected to $v_k$, since otherwise $v_{i+1} v_1 v_2 ... v_i v_k v_{k-1} ... v_{i+2}$ is a cycle of length $k$. It follows that the sets $\{ v_i : v_1 \sim v_i \}$ and $\{ v_{i+1} : v_i \sim v_k \}$ are disjoint subsets of $\{ v_2, ... v_k \}$, but by assumption their union must have size at least $n$ (this step also works under the weaker assumption that $d_v + d_w \ge n$ for each $v \neq w$); contradiction.

share|improve this answer
    
If you have time, I would really appreciate that! –  Elliott Dec 20 '10 at 19:12
1  
Note also that the bound n/2 is sharp; if n is even, the disjoint union of two copies of K_{n/2} is not Hamiltonian and if n is odd, the "wedge sum" of two copies of K_{(n+1)/2} is not Hamiltonian. –  Qiaochu Yuan Dec 20 '10 at 22:35
    
Thanks, this is quite nice! MUCH nicer than trying to remove someone while maintaining enough friends for the remaining people (in the case where n is even). –  Elliott Dec 21 '10 at 6:22

http://www.math.uri.edu/~eaton/GT4F03.pdf

Has a simple proof: Theorem 6

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.