Kneser graph
The Kneser graphK(5, 2), isomorphic to thePetersen graph
Named after	Martin Kneser
Vertices	${\displaystyle (\genfrac{}{}{0ex}{}{n}{k})}$
Edges	${\displaystyle \frac{1}{2}(\genfrac{}{}{0ex}{}{n}{k})(\genfrac{}{}{0ex}{}{n-k}{k})}$
Chromatic number
Properties	${\displaystyle (\genfrac{}{}{0ex}{}{n-k}{k})}$-regular arc-transitive
Notation	K(n,k),KGn,k.
Table of graphs and parameters

Ingraph theory, theKneser graphK(n,k) (alternativelyKG_n,k) is thegraph whosevertices correspond to thek-element subsets of a set ofn elements, and where two vertices are adjacentif and only if the two corresponding sets aredisjoint. Kneser graphs are named afterMartin Kneser, who first investigated them in 1956.

The Kneser graphK(n, 1) is thecomplete graph onn vertices.

The Kneser graphK(n, 2) is thecomplement of theline graph of the complete graph onn vertices.

The Kneser graphK(2n − 1,n − 1) is theodd graphO_n; in particularO₃ =K(5, 2) is thePetersen graph (see top right figure).

The Kneser graphO₄ =K(7, 3), visualized on the right.

The Kneser graph${\displaystyle K(n,k)}$ has${\displaystyle (\genfrac{}{}{0ex}{}{n}{k})}$ vertices. Each vertex has exactly${\displaystyle (\genfrac{}{}{0ex}{}{n-k}{k})}$ neighbors.

The Kneser graph isvertex transitive andarc transitive. When${\displaystyle k=2}$, the Kneser graph is astrongly regular graph, with parameters${\displaystyle ((\genfrac{}{}{0ex}{}{n}{2}),(\genfrac{}{}{0ex}{}{n-2}{2}),(\genfrac{}{}{0ex}{}{n-4}{2}),(\genfrac{}{}{0ex}{}{n-3}{2}))}$. However, it is not strongly regular when${\displaystyle k>2}$, as different pairs of nonadjacent vertices have different numbers of common neighbors depending on the size of theintersection of the corresponding pairs of sets.

Because Kneser graphs areregular andedge-transitive, theirvertex connectivity equals theirdegree, except for${\displaystyle K(2k,k)}$ which isdisconnected. More precisely, the connectivity of${\displaystyle K(n,k)}$ is${\displaystyle (\genfrac{}{}{0ex}{}{n-k}{k}),}$ the same as the number of neighbors per vertex.^[1]

As Kneser (1956)conjectured, thechromatic number of the Kneser graph${\displaystyle K(n,k)}$ for${\displaystyle n\ge 2k}$ is exactlyn − 2k + 2; for instance, the Petersen graph requires three colors in anyproper coloring. This conjecture wasproved in several ways.

• László Lovász proved this in 1978 usingtopological methods,^[2] giving rise to the field oftopological combinatorics.
• Soon thereafterImre Bárány gave a simple proof, using theBorsuk–Ulam theorem and a lemma ofDavid Gale.^[3]
• Joshua E. Greene won the 2002Morgan Prize for outstanding undergraduate research for his further-simplified but still topological proof.^[4]
• In 2004,Jiří Matoušek found a purelycombinatorial proof.^[5]

In contrast, thefractional chromatic number of these graphs is${\displaystyle n/k}$.^[6]When,${\displaystyle K(n,k)}$ has no edges and its chromatic number is 1. When${\displaystyle n=2k}$, the graph is a perfect matching and its chromatic number is 2.

It is well-known that thePetersen graph is notHamiltonian, but it was long conjectured that this was the sole exception and that every other connected Kneser graphK(n,k) is Hamiltonian.

In 2003, Chen showed that the Kneser graphK(n,k) contains aHamiltonian cycle if^[7]

${\displaystyle n\ge \frac{1}{2}\left(3k+1+\sqrt{5k^2-2k+1}\right).}$

Since

holds for all${\displaystyle k}$, this condition is satisfied if

${\displaystyle n\ge \left(\frac{3+\sqrt{5}}{2}\right)k+1\approx 2.62k+1.}$

Around the same time, Shields showed (computationally) that, except the Petersen graph, all connected Kneser graphsK(n,k) withn ≤ 27 are Hamiltonian.^[8]

In 2021, Mütze, Nummenpalo, and Walczak proved that the Kneser graphK(n,k) contains a Hamiltonian cycle if there exists a non-negativeinteger${\displaystyle a}$ such that${\displaystyle n=2k+2^a}$.^[9] In particular, theodd graphO_n has a Hamiltonian cycle ifn ≥ 4. Finally, in 2023, Merino, Mütze and Namrata completed the proof of the conjecture.^[10]

Whenn < 3k, the Kneser graphK(n,k) contains no triangles. More generally, whenn <ck it does not containcliques of sizec, whereas it does contain such cliques whenn ≥ck. Moreover, although the Kneser graph always containscycles of length four whenevern ≥ 2k + 2, for values ofn close to2k the shortestodd cycle may have variable length.^[11]

Thediameter of a connected Kneser graphK(n,k) is^[12]$${\displaystyle \lceil \frac{k-1}{n-2k}\rceil +1.}$$

Thespectrum of the Kneser graphK(n,k) consists ofk + 1 distincteigenvalues:$${\displaystyle {\lambda }_j=(-1{)}^j(\genfrac{}{}{0ex}{}{n-k-j}{k-j}),j=0,\dots ,k.}$$Moreover${\displaystyle {\lambda }_j}$ occurs withmultiplicity${\displaystyle (\genfrac{}{}{0ex}{}{n}{j})-(\genfrac{}{}{0ex}{}{n}{j-1})}$ for${\displaystyle j>0}$ and${\displaystyle {\lambda }_0}$ has multiplicity 1.^[13]

TheErdős–Ko–Rado theorem states that theindependence number of the Kneser graphK(n,k) for${\displaystyle n\ge 2k}$ is$${\displaystyle \alpha (K(n,k))=(\genfrac{}{}{0ex}{}{n-1}{k-1}).}$$

TheJohnson graphJ(n,k) is the graph whose vertices are thek-element subsets of ann-element set, two vertices being adjacent when they meet in a(k − 1)-element set. The Johnson graphJ(n, 2) is the complement of the Kneser graphK(n, 2). Johnson graphs are closely related to theJohnson scheme, both of which are named afterSelmer M. Johnson.

Thegeneralized Kneser graphK(n,k,s) has the same vertex set as the Kneser graphK(n,k), but connects two vertices whenever they correspond to sets that intersect ins or fewer items.^[11] ThusK(n,k, 0) =K(n,k).

Thebipartite Kneser graphH(n,k) has as vertices the sets ofk andn −k items drawn from a collection ofn elements. Two vertices are connected by an edge whenever one set is a subset of the other. Like the Kneser graph it is vertex transitive with degree${\displaystyle (\genfrac{}{}{0ex}{}{n-k}{k}).}$ The bipartite Kneser graph can be formed as abipartite double cover ofK(n,k) in which one makes two copies of each vertex and replaces each edge by a pair of edges connecting corresponding pairs of vertices.^[14] The bipartite Kneser graphH(5, 2) is theDesargues graph and the bipartite Kneser graphH(n, 1) is acrown graph.

• Weisstein, Eric W."Kneser Graph".MathWorld.
• Weisstein, Eric W."Odd Graph".MathWorld.

• Parametric families of graphs
• Regular graphs

• CS1 maint: archived copy as title
• Articles with short description
• Short description is different from Wikidata