Beispiele

• vollständiger binärer Baum:

  $\Sigma$ = {0, 1}, V = $\Sigma^{\le k}_{}$, E = {{w, wa} | w $\in$ $\Sigma^{< k}_{}$, a $\in$ $\Sigma$}.

• Hyperwürfel:

  V = $\Sigma^{k}_{}$, E = {xy | dist(x, y) = 1}

  wobei dist(x, y) = |{i | 0$\le$i < k : x_i $\neq$ y_i}|
  (Anzahl unterschiedlicher Bits)

• Petersen-Graph: M = {1, 2, 3, 4, 5}, V = M$\choose2$, E = {xy | x $\cap$ y = $\emptyset$}

  beachte: E $\subseteq$ V$\choose2$ = M$\choose2$$\choose2$

Aufgaben: beweise direkt aus der Definition:

• Hyperwürfel enthält keinen ungeraden C_k
• Petersen-Graph enthält kein K₃