proving my induction in game theory doubt

Question

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?

Answer 1

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$.