Question

Prove or disprove the following:

1. For any (non-directed) graph, the number of odd-degree nodes is even.
2. In a minimally connected graph of n>2 nodes with exactly k nodes of degree 1 ,  1<k<n. I.e., you cannot have a minimally connected graph with 1 node of degree 1 or n nodes of degree 1.
   

Answer 1

Please note that I am proving the first question here. Please post second question as a seperate question.

To Prove: For any (non-directed) graph, the number of odd-degree nodes is even.

Proof: In words, we can prove it by stating the following facts: 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.

Mathematically, we can prove it as follows:

Let G be a graph with 'e' edges and 'n' vertices vi,v2, V3,. . . ,vn. Since each edge is incident on two vertices, it contributes 2to 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, TL degree(va) 2. i-1 Let the degrees of first r vertices be even and the remaining (n r) vertices have odd degrees,then clearly,E: 1 degree(Vi)-evenSince. TL degree(vdegree(vdegree(v) i-1 i-1 t 4-1 i degree(vi) _ ΣΙ i degree(Vi ) Ση TH degree(Vijs even.(WHY?) i 1 Ση ril degree (vi) But, the fori r1,r + 2,..., n each d(vi) is odd. So, the number of terms in Ση ri 1 degree( In lucid words, (n Hence the result. Ui must be even - r) is even.

Please let me know in the comments if you have any doubts or concerns. Thank you.