Solution to Proof that an undirected graph has an even number of vertices of odd degree. - Sikademy
Author Image

Archangel Macsika

Proof that an undirected graph has an even number of vertices of odd degree.

The Answer to the Question
is below this banner.

Can't find a solution anywhere?


Get the Answers Now!

You will get a detailed answer to your question or assignment in the shortest time possible.

Here's the Solution to this Question

Lets define graph G = (V, E), where V - set of verticles, E - set of edges. Since each edge connects two verticles(technically, the loop connects verticle with itself, but it increases the degree of verticle by 2, so that doesn't ruin the logic as we will se), then

\sum_{v \in V} deg(v) = 2|E| - sum of degrees of all verticles equals to doubled number of edges, so this sum is even.

Let V_1\subset V , V_2\subset V be a subset of all verticles with even and odd degree number respectively, then \sum_{v \in V_1} deg(v) is obviously even. Since \sum_{v \in V_1} deg(v)+\sum_{v \in V_2} deg(v)=\sum_{v \in V} deg(v)\implies \sum_{v \in V_2} deg(v)=\sum_{v \in V} deg(v)-\sum_{v \in V_1} deg(v)

Then \sum_{v \in V_2} is even. Every value in that sum(if it is not empty) is odd, then amount of values must be even. Amount of values in that sum is amount of verticles with odd degree number. If that sum is empty, then the amount of verticles with odd degree is 0 - still even number

The statement has been proven

Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers

Question ID: mtid-5-stid-8-sqid-722-qpid-607