Exercise · ZW-DEGREE-OF-A-VERTEX-005 · ★★☆ Intermediate
Which of these lists can be the degree list of a simple graph?
Choose one option.
Show answer
- B. 3, 3, 2, 2
Explanation
It comes from removing one edge from a complete graph on 4 vertices. 3,3,3,1 is impossible (three vertices of degree 3 touch the fourth); 3,2,2 has odd sum; in 4,2,2,1 a vertex of degree 4 would need 5 vertices.
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-006 What is the degree of each vertex of the complete graph K_6?
- ZW-DEGREE-OF-A-VERTEX-007 A graph has 7 vertices. Which of these numbers can NOT be the number of vertices of odd degree?
- 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…