title: Graphe biparti de Kneser
text: # 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.
  
  