For the kneser graphs $K(n,k)$. The vertices of $K(n, k)$ are all $k-$subsets of the set $\{1, 2 ,......,n \}$ and two vertices are adjacent to each other if and only if the $k-$subsets are disjoint.
First, I want know which values of $k$ is $K(n,k)$ the empty graph ?
First I know that the number of vertices in $K(n,k)$ is simply ${n \choose k}$ which is the number of subsets of size $k$ from $ \{1,2,....,n \}$, and further, The degree of each vertex is nothing but ${n-k \choose k }$ because for example if we have $n=5$ and $k =2$ then $\{1,2\} \to \{3,4 \},\{4,5\},\{3,5\}$ , More formally, when we have a vertex $v$, it can map to other vertex where non of the elements intersect and so we it maps $k-subsets$ from remaining $n-k$, Now as we can see for this to make sense we must have that $n - k \geq k$ and so $n \geq 2k$ and so $\frac{n}{2} \geq k$ and so the empty graph will happen whenever $$\frac{n}{2} < k $$, is that correct ?
Secondly, I wanted to show that if $n \geq 3k -1$, then $K(n,k)$ is connected.
This will only happen if I am to show that there exists a path between any two vertices in the graph, but I am stuck here on how to prove this, any suggestions ?
If $2k=k+k>n$, two subsets of $[1,n]$ with cardinality $k$ cannot be disjoint by the Dirichlet box principle. If $n\geq 3k$, there is a path of length $2$ between any two nodes of the graph, associated with two subsets $A,B$: $$ A \longrightarrow T\subseteq [1,n]\setminus(A\cup B) \longrightarrow B $$ since $[1,n]\setminus(A\cup B)$ has at least $k$ elements. On the other hand, if $A$ and $B$ are disjoint there is a direct path between them, $A\longrightarrow B$, so in the previous lines we may assume without loss of generality that $|A\cap B|\geq 1$, so $|A\cup B|\leq 2k-1$ and the condition $n\geq 3k-1$ is enough to ensure a connected graph.
Anyway, $KG(n,k)$ is connected as soon as $n\geq 2k+1$. An example with $k=3,n=7$, $A=\{1,2,3\},B=\{3,4,5\}$:
$$ A=\{1,2,3\}\to \{5,6,7\}\to \{1,3,4\}\to \{2,6,7\}\to \{3,4,5\}=B.$$