Graphe biparti de Kneser
# Graphe biparti de Kneser

En théorie des graphes, une branche des mathématiques, les graphes bipartis de Kneser $H_{n,k}$ forment une famille de graphes non orientés définie comme suit :

Soient E un ensemble à n éléments et k un entier inférieur à n. Les sommets du graphe $H_{n,k}$ représentent les sous-ensembles de E à k éléments ou à n − k éléments. Deux sommets sont reliés par une arête lorsque l'un des sous-ensembles qu'ils représentent est inclus dans l'autre.

## Exemples

Le graphe biparti de Kneser $H_{5,2}$ est le graphe de Desargues (figure).

Les graphes bipartis de Kneser $H_{n,1}$ sont les graphes couronnes.

## Propriétés

Le graphe biparti de Kneser a $2C_{k}^{n}$ sommets. Il est régulier de degré $C_{k}^{n-k}$.

Comme le Graphe de Kneser, il est sommet-transitif.

Le graphe biparti de Kneser $H_{n,k}$ peut être formé comme une double couverture bipartie (en) du graphe de Kneser $KG_{n,k}$ en dupliquant chaque sommet et en remplaçant chaque arête par une paire d'arêtes reliant les paires correspondantes de sommets.

