Exercise · ZW-DEGREE-OF-A-VERTEX-010 · ★★★ Advanced
Is there a simple graph with 5 vertices in which every vertex has degree 3?
Choose one option.
Show answer
- A. No: the degree sum would be 15, which is odd
Explanation
The degree sum is twice the number of edges, hence even. Here it would be 5·3 = 15, impossible. K5 has degree 4 and the cycle degree 2.
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-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?