# Kneser graphs

Let $k,n$ be positive integers with $k\le n$. The *Kneser graph ^{}* ${K}_{n:k}$ has as its vertex set the $\left(\genfrac{}{}{0pt}{}{n}{k}\right)$ $k$-element subsets of $\{1,2,\mathrm{\dots},n\}$. Two vertices are adjacent if and only if they correspond to disjoint subsets.

The graph ${K}_{n:1}$ is the complete graph^{} on $n$ vertices. Another well-known Kneser graph is ${K}_{5:2}$, better known as the *Petersen graph ^{}*, which is shown in figure 1. The Petersen graph is often a counterexample to graph-theoretical conjectures.

Title | Kneser graphs |
---|---|

Canonical name | KneserGraphs |

Date of creation | 2013-03-22 14:16:49 |

Last modified on | 2013-03-22 14:16:49 |

Owner | justice (4961) |

Last modified by | justice (4961) |

Numerical id | 5 |

Author | justice (4961) |

Entry type | Definition |

Classification | msc 05C99 |

Defines | Petersen graph |