Graphs Built from Set Systems (Kneser-type)

The construction

Fix an $n$-element ground set $X$. Build a graph $G$ whose vertices are the $k$-subsets of $X$, and join two vertices $A,B$ by an edge whenever their intersection has a fixed prescribed size $t$: $A \sim B \iff |A \cap B| = t.$ There are $\binom{n}{k}$ vertices. The famous Kneser graph $K(n,k)$ is the special case $t=0$ (disjoint $k$-sets); the konkur question uses $k=3,\ t=1$.

Why it is always regular

The count of neighbors of a vertex $A$ does not depend on which $k$-set $A$ is — by symmetry of $X$. To build a neighbor $B$ of $A=\{a_1,\dots,a_k\}$ you:

1. choose the $t$ elements $B$ keeps inside $A$: $\binom{k}{t}$ ways;
2. choose the remaining $k-t$ elements of $B$ from the $n-k$ elements outside $A$: $\binom{n-k}{\,k-t\,}$ ways.

So every vertex has the same degree $\deg(A) = \binom{k}{t}\binom{n-k}{\,k-t\,},$ and therefore $G$ is regular — the structural fact that makes these graphs exam-friendly.

Edge count via the handshake lemma

A regular graph on $N$ vertices of degree $d$ has $\tfrac{1}{2}Nd$ edges: $|E(G)| = \frac{1}{2}\binom{n}{k}\binom{k}{t}\binom{n-k}{\,k-t\,}.$ The product often collapses with the subset-of-a-subset identity $\binom{n}{k}\binom{k}{t}=\binom{n}{t}\binom{n-t}{\,k-t\,}$, or by choosing the union first: pick the $2k-t$ elements that $A\cup B$ touches, then split them, giving a clean closed form.

Worked mini-example ($k=3,\ t=1$)

Degree: $\binom{3}{1}\binom{n-3}{2}=3\binom{n-3}{2}$. Edges: $|E| = \tfrac{1}{2}\binom{n}{3}\cdot 3\binom{n-3}{2}.$ Now regroup by the 5 elements that $A\cup B$ uses (since $|A\cup B|=3+3-1=5$): $\binom{n}{3}\binom{n-3}{2}=\binom{n}{5}\binom{5}{3}=10\binom{n}{5}$, so $|E| = \tfrac{3}{2}\cdot 10\binom{n}{5} = 15\binom{n}{5}.$ The smallest case $n=5,\ k=3,\ t=1$ is $3$-regular on $\binom{5}{3}=10$ vertices with girth $5$ — exactly the Petersen graph, the textbook non-Hamiltonian example.

Exam trick: Regularity, degree, and edge count come for free from binomials — but "deeper" properties (Hamiltonicity, diameter, chromatic number) do not scale uniformly. When a choice claims a property holds "for every $n$," test the smallest legal $n$ first; here $n=5$ gives the Petersen graph, instantly killing any universal Hamiltonicity claim.