---
tag: DXHTCMW7E4
kind: concept
name: Kneser graph
aliases: [bipartite-kneser-graph, generalized-kneser-graph, kneser-conjecture, kneser-graphs, knesers-conjecture]
sources:
  - wikipedia: en:2724154@r1362915729
    locator: Kneser graph
    note: adopted
    mention: wikipedia://en/2724154
    sections: [Summary]
same_as:
  wikidata: Q733004
  wikipedia: Kneser graph
inventory: [2FCPX1W98H]
---

## Summary

In graph theory, the **Kneser graph** $K(n, k)$ (alternatively $KG_{n,k}$) is the [[graph|00C0BR7D7H]] whose vertices correspond to the [[$k$-element subsets of a set of $n$ elements|098PHYBTV9]], and where two vertices are adjacent if and only if the two corresponding sets are [[disjoint|0W4RPA8QH3]]. Kneser graphs are named after Martin Kneser, who first investigated them in 1956.