22
$\begingroup$

I'm having a bit of a trouble with the below question

Given $G$ is an undirected graph, the degree of a vertex $v$, denoted by $\mathrm{deg}(v)$, in graph $G$ is the number of neighbors of $v$.
Prove that the number of vertices of odd degree in any graph $G$ is even.

  • 0
    @Mike I tried to formalize it.2013-11-20

8 Answers 8

31

I'm posting Mike's comment as an answer, since he won't.

The sum of all the degrees is equal to twice the number of edges. Since the sum of the degrees is even and the sum of the degrees of vertices with even degree is even, the sum of the degrees of vertices with odd degree must be even. If the sum of the degrees of vertices with odd degree is even, there must be an even number of those vertices.

10

Let G be a graph with $'e'$ edges and $'n'$ vertices $v_1,v_2,v_3,...,v_n$. Since each edge is incident on two vertices, it contributes $2$to the sum of degree of vertices in graph $G$. Thus the sum of degrees of all vertices in $G$ is twice the number of edges in $G$. Hence, $\sum_{i=1}^n\text{degree}(v_i)= 2e.$ Let the degrees of first $r$ vertices be even and the remaining $(n-r)$ vertices have odd degrees,then clearly,$\sum_{i=1}^{r}\text{degree}(v_i)= even $.Since,$\sum_{i=1}^n\text{degree}(v_i)= \sum_{i=1}^r\text{degree}(v_i)+\sum_{i=r+1}^n\text{degree}(v_i)$ $\implies$ $\sum_{i=1}^n\text{degree}(v_i)- \sum_{i=1}^r\text{degree}(v_i)=\sum_{i=r+1}^n\text{degree}(v_i)$

$\implies$ $\sum_{i=r+1}^n\text{degree}(v_i)$ is even.($WHY?$)

But, the for $i=r+1,r+2,...,n$ each $d(v_i)$ is odd. So, the number of terms in $\sum_{i=r+1}^n\text{degree}(v_i)$ must be even.

In lucid words,$(n-r)$ is even.

Hence the result.

  • 0
    Looks nice to me. FYI, I was not the downvoter, and I am now an upvoter!2017-04-27
3

We represent $G$ by a symmetric relation on the set of points $P$, which we also call $G$, so $G = \{(a,b), (b,a) : \text{there is an edge between } a \text{ and } b\}$ Clearly, $\#G |2$ where $\#G$ is the number of elements in $G$. Now $\deg (a) = \# \{(a,x): (a,x) \in G\}$ Since we have $\sum_{a\in P} \deg(a) = \sum_{a\in P} \# \{(a,x): (a,x) \in G\} = \#\{(x,y) : (x,y) \in G\} = \# G$ We know $\sum_{a\in P} \deg (a) | 2$ From number theory we have $\sum_{j=1}^n a_j |2 \Leftrightarrow \#\{a_j : a_j \not|\, 2\}|2$ (the number of odd numbers in a sum is even, iff the sum is even) and setting $a_j = \deg(b_j)$ with $b_j \in P$ an enumeration of $P$, the statement follows.

2

Hint: What is the sum of the degrees of all vertices?

1

Suppose we have an arbitrary graph with $l$ vertices. Suppose we have $n$ vertices with odd degree. Let's consider what happens when we connect(or remove) an edge between any two vertices, there're two possibilities:

1) The two vertices are both of even(or odd) degree: Suppose both vertices are even degree. Connecting(or removing) an edge between them will increase the degree of both vertices by $1$ (or decrease in case of removing an edge), therefore both vertices will become odd degree, and $n$ will increase by $2$.

Similarly, if the two vertices were initially odd degree, then connecting(or removing) an edge will turn both of the vertices into even degree, and $n$ will decrease by $2$.

2) One vertex is odd while the other is even. In this case, connecting(or removing) an edge will turn the odd vertex into an even one, and the odd vertex becomes even. Therefore $n$ will remain unchanged.

From this we learn that the number of odd degree vertices $n$ can only increase/decrease in steps of $2$(or remain unchanged) as we create(remove) edges.

Now when we construct any graph we wish, we start with our vertices isolated from each other with not a single connection(edge). Therefore, initially $n=0$(all vertices are of even degree since not a single edge connects them) , and as we make connections, it can only increase/decrease in steps of $2$, therefore $n$ will remain even.

0

The degree or valency or order of any vertex is the number of edges or arcs or lines connected to it. The sum of degrees of any graph can be worked out by adding the degree of each vertex in the graph.

The sum of degrees is twice the number of edges. Therefore, the sum of degrees is always even. The sum of an odd number of odd numbers is always equal to an odd number and never an even number(e.g. odd+odd+odd=odd or 3*odd).

Taking into account all the above rules and/or information, a graph with an odd number of vertices with odd degrees will equal to an odd number. Since it is not possible to draw a graph if its sum of degrees is odd, this graph cannot be drawn.

-1

Simply, sum of even numbers of odd number is an even number (always odd+odd=even and even+odd=odd and even+even=even). As the sum of degree of vertices needs to be even number, number of such vertices must be even. Which @Mike has presented very succinctly.

  • 1
    Welcome to this site! The question you just answered is rather old and already has perfectly good answers, to which your post doesn't seem to add much. More value to the site would be added by answering unanswered questions, or giving answers significantly different to the ones already existing.2015-06-30