1
$\begingroup$

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?

$\endgroup$
1
2
$\begingroup$

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

$\endgroup$
9
  • $\begingroup$ 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. $\endgroup$ Feb 6 '15 at 21:46
  • $\begingroup$ @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}\}$$ $\endgroup$
    – AlexR
    Feb 6 '15 at 21:49
  • $\begingroup$ 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. $\endgroup$ Feb 6 '15 at 21:55
  • $\begingroup$ What do you mean by the ‘central’ page? $\endgroup$ Feb 6 '15 at 21:56
  • 1
    $\begingroup$ @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. $\endgroup$ Feb 6 '15 at 22:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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