Ungerichteter Graph/Kantengraph/Kantenanzahl/Fakt/Beweis

Beweis
  1. Dies folgt unmittelbar aus der Definition des Kantengraphen.
  2. Es sei eine Kante von , aufgefasst als Punkt im Kantengraph . Dieser Punkt ist mit einem anderen Punkt des Kantengraphen, also einer Kante des Ausgangsgraphen, genau dann verbunden, wenn diese Kante an oder an anliegt, wobei nur eines der Fall sein kann. Die Anzahl der an anliegenden Kanten ist , allerdings dürfen wir die Kante nicht mitzählen.
  3. Nach Fakt ist die gesuchte Anzahl der Kanten in unter Verwendung von Teil (2) gleich

    da in der mittleren Summe der Term so oft vorkommt, wie es angibt.