Ungerichteter Graph/Kantengraph/Kantenanzahl/Fakt/Beweis

Beweis

Dies folgt unmittelbar aus der Definition des Kantengraphen.
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.
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.

This article is issued from Wikiversity. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.