Alex's Notes

Vertex degree sum in a graph

2 min read

Lemma

Let represents a undirected simple graph. Let be the degree of vertex . Then

Proof

Lets prove this by induction on the number within a graph.

Suppose a graph has no edges. Therefore for all as there are no edges to be incident to . Thus Suppose we have shown the statement true for all graphs where and suppose we have a graph with . Pick any edge and remove it from the graph to get . From the induction hypothesis we have Where is the degree in . Note that for all . Whereas, for (as it is incident to as well as all the edges in ). Therefore

Misplaced &\sum_{v \in V} \mbox{deg}_{G}(v) & = \sum_{v \in V \backslash \{x,y\}} \mbox{deg}_{G^{\ast}}(v) + \sum_{v \in \{x,y\}} (\mbox{deg}_{G}(v) + 1)\\ & = 2 + \sum_{v \in V} \mbox{deg}_{G^{\ast}}(v) \\ & = 2 + 2 (\vert E \vert - 1)\\ & = 2 \vert E \vert. \end{align*}$$ This shows the inductive case and proves the statement.

Graph View