Let n ≥ 2 be an integer. Form a graph $G_n$ whose vertices are all the two-element subsets of {$1, 2, . . . , n$}. In this graph, we have an edge between distinct vertices {a, b} and {c, d} exactly when {a, b} ∩ {c, d} = ∅. For which values of $n \geq 2$ is $G_n$ connected?
There has been an answer to this that I found online, in question 48.4 on this PDF (http://euclid.colorado.edu/~roymd/m2001/sols13.pdf). But I don't understand the cases. Particularly, it seems to me that this proof answers the question knowing already that the answer is $n \geq 5$ which makes it intuitively harder for me to understand how to get to that answer.
Can someone explain this problem and the answers to me?
When solving problems (contest or research or whatever), a good approach is to make conjectures/assumptions and try to prove them (or fail to prove them, giving you more insight).
Coming up with good conjectures which lead to the answers you seek comes with trying to solve various problems.
In this case, the question itself asks for which values of $n$ is $G_n$ connected, so it is natural to consider various values of $n$.
Also intuitively, the more the $n$, the more the chances of connecting the two sets via intermediate disjoints sets.
For instance if $n \ge 6$, then given $u = \{a,b\}$ and $v = \{c,d\}$ we can always pick $w = \{e,f\}$ such that $e,f$ are distinct from any of $a,b,c,d$, and thus there is a path from $u$ to $v$ via $w$.
Now all that remains is to consider $n=2,3,4,5$. For $n=2,3,4$ we can easily figure out if $G_n$ is connected or not.
For $n=5$, we just consider the cases where $a,b,c,d$ are all distinct or not (split into cases).
The proof in the pdf for $n=5$ also carries over for $n=6$, so is just written for $n \ge 5$.
Not sure if this helped.