En komplett bipartit graf är inom grafteori en särskild bipartit graf där varje nod i ena nodmängden är ansluten till alla noder i den andra nodmängden.
Definition
En komplett bipartit graf är en graf sådan att det inte finns några bågar mellan två noder om båda noderna ligger i samma nodmängd, eller (grafen är bipartit), men om två noder u och v ligger i varsin nodmängd, respektive , så är bågen uv ett element i E.
Om har storlek m och har storlek n brukar G betecknas
Exempel
För alla k kallas för stjärngrafer. I bilden syns .