# proving my induction in game theory doubt

Highly connected website problem Suppose we have n websites such that for every pair of websites A and B, either A has a link to B or B has a link to A. Prove by induction that there exists a website that is reachable from every other website by clicking at most 2 links.

I am not sure of how to approach this problem especially by induction. What will be our hypothesis for this?

The base case $n=1$ is trivial (there's only one website)
For the induction step assume we have $n$ pages linked such that page $P_i$ is the "central" page (The page wich can be reached from all other $n-1$ pages within at most two clicks). Now add another page $P_{n+1}$. By assumption, either there is a link $P_i\leftarrow P_{n+1}$, wich makes it trivial, or a link $P_{n+1}\leftarrow P_i$ in wich case you need to look at other links as well. We get two cases:

1. $P_{n+1} \leftarrow P_j$ for all $1\le j\le n$ ($P_{n+1}$ is linked by everything). Then we are done with $P_{n+1}$ as the new central.
2. Some page with $P_k\leftarrow P_{n+1}$ is directly linked by $P_i\leftarrow P_k\leftarrow P_{n+1}$. Then we are done as well with $P_i$ remaining central.
3. All pages $P_k\leftarrow P_{n+1}$ also have the link $P_k \leftarrow P_i$. This is the interesting case.

Does that provide a good start?

Formalism
If two pages $P_i$ and $P_j$ are linked from $P_i$ to $P_j$, we write $P_i \to P_j$. If $P_j$ links to $P_i$, we write $P_i \leftarrow P_j$. This allows us to formalise the proposition:

Let $W=\{P_i, 1\le i\le n\}$ be a set of websites such that for every $i\ne j$, either $P_i \to P_j$ or $P_i \leftarrow P_j$ (cf. $(2)$). Then there is a website $P_c\in W$ (called the central website) for wich $$\forall P\in W: [P=P_c \vee P\to P_c \vee \exists P'\in W: [P\to P'\to P_c]] \tag1$$

The proof then proceeds by induction on $n=|W|$.
The base case $n=1$ is $W = \{P_1\}$ so there is only one site, $P_c = P_1$. The induction hypothesis is now that given a set of websites $W$ with $|W| = n$ and $$\forall P\ne P'\in W : [P\to P' \vee P\leftarrow P']\tag2$$ The proposition $(1)$ holds (we may even assume this for $|W| \le n$ if we need to).
The inductive step now assumes $|W|= n+1$ and $(2)$. Removing any page from $W$ will give a set of websites wich satisfies the inductive hypothesis. Using this we must show that $(1)$ also holds for $W$.

• This is very useful, i got the hypothesis to be assumed i have doubt in the two cases that we get here i didnt get how Pn+1 links everything and i am not able to follow case 2. Feb 6 '15 at 21:46
• @RohitGulabwani The requirement is that for any $j$, either $P_j\to P_{n+1}$ or $P_{n+1}\to P_j$. So we must look at the structure of the sets $$\{P_j | P_{n+1}\to P_j\} \text{ and } \{P_j | P_j\to P_{n+1}\}$$ Feb 6 '15 at 21:49
• Still i am not able to get. Thanks for your time though. I wish if you can give a more detailed explanation i am a bit new to such proof's by induction. Feb 6 '15 at 21:55
• What do you mean by the ‘central’ page? Feb 6 '15 at 21:56
• @AlexR: You mean the one that is reachable from every other page in at most two clicks? In that case you need to turn your arrows around. Feb 6 '15 at 22:21