1: . What is the minimum number of vertices of odd degree for any simple graph?

Question

1: . What is the minimum number of vertices of odd degree for any simple graph? .cea ideea simple graph. The introduction of an edge to this simple graph can either connect two already existing vertices, or connect one new vertex to one existing vertex. For any simple graph, this has an effect on the number of vertices of odd degree. Create a brief table of all the various possibilities and use this to demonstrate that the number of vertices of odd degree in a simple graph is always an even number.

Explanation / Answer

minimum number of vertices of odd degree: SEE methods to prove it:

method 1: ( USING HAND SHAKING LEMMA FOR DEGREE SUM FORMULA)

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.

uler's proof of the degree sum formula uses the technique of double counting: he counts the number of incident pairs (v,e) where e is an edge and vertex v is one of its endpoints, in two different ways. Vertex v belongs to deg(v) pairs, where deg(v) (the degree of v) is the number of edges incident to it. Therefore, the number of incident pairs is the sum of the degrees. However, each edge in the graph belongs to exactly two incident pairs, one for each of its endpoints; therefore, the number of incident pairs is 2|E|. Since these two formulas count the same set of objects, they must have equal values.

In a sum of integers, the parity of the sum is not affected by the even terms in the sum; the overall sum is even when there is an even number of odd terms, and odd when there is an odd number of odd terms. Since one side of the degree sum formula is the even number 2|E|, the sum on the other side must have an even number of odd terms; that is, there must be an even number of odd-degree vertices.

Alternatively, it is possible to use mathematical induction to prove that the number of odd-degree vertices is even, by removing one edge at a time from a given graph and using a case analysis on the degrees of its endpoints to determine the effect of this removal on the parity of the number of odd-degree vertices.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.