Zu zwei Graphen G = ( V , E ) {\displaystyle {}G=(V,E)} und H = ( W , F ) {\displaystyle {}H=(W,F)} nennt man den Graphen mit Knotenmenge V × W {\displaystyle {}V\times W} , wobei zwischen zwei Knoten ( v 1 , w 1 ) {\displaystyle {}(v_{1},w_{1})} und ( v 2 , w 2 ) {\displaystyle {}(v_{2},w_{2})} genau dann eine Kante besteht, wenn entweder v 1 = v 2 {\displaystyle {}v_{1}=v_{2}} und { w 1 , w 2 } ∈ F {\displaystyle {}\{w_{1},w_{2}\}\in F} oder w 1 = w 2 {\displaystyle {}w_{1}=w_{2}} und { v 1 , v 2 } ∈ E {\displaystyle {}\{v_{1},v_{2}\}\in E} gilt, das kartesische Produkt der Graphen.
und 
nennt man den Graphen mit Knotenmenge 
, wobei zwischen zwei Knoten
und 
genau dann eine Kante besteht, wenn entweder
und
oder
und
gilt, das
kartesische Produkt
der Graphen.
