Degrees of Vertices in Graphs Quiz

1) In an undirected graph, the degree of a vertex is:

The number of vertices in the graph

The number of edges incident with the vertex

The number of paths starting at the vertex

The length of the longest path through the vertex

Degree counts how many edges touch the vertex.

Explanation

Degree counts how many edges touch the vertex.

2) In an undirected graph, a loop at a vertex contributes 2 to the degree of that vertex.

True

False

A loop has two ends at the same vertex.

Explanation

A loop has two ends at the same vertex.

3) A vertex (v) is incident with edges (vw_1, vw_2, vw_3) and one loop at (v). What is deg(v)?

3

4

5

6

Three regular edges contribute 3, the loop contributes 2 → total 5.

Explanation

Three regular edges contribute 3, the loop contributes 2 → total 5.

4) Consider the path graph (P4) (4 vertices in a line). What are the degrees of its vertices?

1,1,1,1

2,2,2,2

1,2,2,1

0,1,2,3

Endpoints have degree 1, internal vertices have degree 2.

Explanation

Endpoints have degree 1, internal vertices have degree 2.

5) In any finite undirected graph, the sum of the degrees of all vertices equals twice the number of edges.

True

False

Handshake lemma: each edge contributes 2 to total degree.

Explanation

Handshake lemma: each edge contributes 2 to total degree.

6) In a simple graph with 6 vertices, each of degree 3, how many edges does the graph have?

9

12

15

18

Total degree (= 6×3=18), so edges (=18/2=9).

Explanation

Total degree (= 6×3=18), so edges (=18/2=9).

7) In any undirected graph, the number of vertices of odd degree is always even.

True

False

Total degree is even → odd-degree vertices occur in pairs.

Explanation

Total degree is even → odd-degree vertices occur in pairs.

8) In a simple graph with n vertices, the maximum possible degree of any vertex is:

N

N−1

N/2

2

A vertex can connect to all other vertices, not itself.

Explanation

A vertex can connect to all other vertices, not itself.

9) In the complete graph (K5), what is the degree of each vertex?

3

4

5

10

Each vertex is adjacent to the other 4.

Explanation

Each vertex is adjacent to the other 4.

10) A star graph with 6 leaves (7 vertices total) has one center and 6 leaves. What is the degree of the center?

1

3

5

6

The center connects to all 6 leaves.

Explanation

The center connects to all 6 leaves.

11) A vertex with no incident edges is called an isolated vertex and has degree 0.

True

False

By definition.

Explanation

By definition.

12) In a simple graph, adding one new edge between two distinct vertices changes:

The degrees of exactly one vertex

The degrees of exactly two vertices

The degrees of all vertices

The number of vertices but not degrees

Each endpoint degree increases by 1.

Explanation

Each endpoint degree increases by 1.

13) A vertex (v) in a multigraph has two loops at (v), and three ordinary edges from (v) to other vertices. What is deg(v)?

3

5

7

8

Two loops contribute 4, plus three edges → total 7.

Explanation

Two loops contribute 4, plus three edges → total 7.

14) A graph has 5 vertices with degrees 2, 2, 3, 3, x. What must x be for this to be possible?

1

2

3

4

Sum must be even: 2+2+3+3+x = 10+x → x must be even; 2 fits within simple graph bounds.

Explanation

Sum must be even: 2+2+3+3+x = 10+x → x must be even; 2 fits within simple graph bounds.

15) In any simple graph with 5 vertices, there must be at least two vertices with the same degree.

True

False

Degrees range only 0–4, but cannot have both 0 and 4 → pigeonhole principle forces repetition.

Explanation

Degrees range only 0–4, but cannot have both 0 and 4 → pigeonhole principle forces repetition.