Ungerichteter Graph/Kantengraph/Kantenanzahl/Fakt/Beweis

Beweis

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

   ${\frac {1}{2}}\sum _{\{u,v\}\in E}{\left(d(u)+d(v)-2\right)}={\frac {1}{2}}\sum _{\{u,v\}\in E}{\left(d(u)-1+d(v)-1\right)}={\frac {1}{2}}\sum _{v\in V}d(v)(d(v)-1)\,,$

   da in der mittleren Summe der Term ${}d(v)-1$ so oft vorkommt, wie es ${}d(v)$ angibt.

Zur bewiesenen Aussage