Exercise · ZW-DEGREE-OF-A-VERTEX-007 · ★★☆ Intermediate
A graph has 7 vertices. Which of these numbers can NOT be the number of vertices of odd degree?
Choose one option.
Show answer
- C. 3
Explanation
The degree sum is even, so the number of odd-degree vertices is always even. 0, 2 and 6 are possible; 3 is not.
Review the concept: Degree of a vertex
The degree \(\deg(v)\) of a vertex \(v\) is the number of edges of the graph (the set \(E\)) that have it as an endpoint.
\[\deg(v)=\bigl|\{e\in E:\ v\in e\}\bigr|\]
More practice problems: degree of a vertex
- ZW-DEGREE-OF-A-VERTEX-001 A graph has vertices 1,2,3,4 and edges \1,2\,\1,3\,\1,4\,\2,3\. What is deg(1)?
- ZW-DEGREE-OF-A-VERTEX-002 A graph has edges ab, ac, ad, bc, de. What is the degree of vertex c?
- ZW-DEGREE-OF-A-VERTEX-003 A graph has 7 edges. What is the sum of the degrees of all its vertices?
- ZW-DEGREE-OF-A-VERTEX-004 A graph has five vertices of degrees 3, 3, 2, 2 and 2. How many edges does it have?
- ZW-DEGREE-OF-A-VERTEX-005 Which of these lists can be the degree list of a simple graph?
- ZW-DEGREE-OF-A-VERTEX-006 What is the degree of each vertex of the complete graph K_6?
- ZW-DEGREE-OF-A-VERTEX-008 A graph has 12 edges and every vertex has degree 3. How many vertices does it have?
- ZW-DEGREE-OF-A-VERTEX-009 A simple graph has 6 vertices and one of them is isolated. What is the largest degree another verte…