In-Depth Degree Analysis in Graph Theory Quiz

1) In a simple undirected graph, the degree of a vertex (v) is:

The number of edges in the graph

The number of neighbours of (v)

The number of paths starting at (v)

The number of loops at (v)

In a simple graph, degree is the number of adjacent vertices.

Explanation

In a simple graph, degree is the number of adjacent vertices.

2) A vertex (v) is adjacent to 4 distinct other vertices and has 2 loops at (v). What is deg(v) in a multigraph?

4

6

8

10

Ordinary edges = 4; loops contribute 2 each → (4 + 2×2 = 8).

Explanation

Ordinary edges = 4; loops contribute 2 each → (4 + 2×2 = 8).

3) An undirected graph has 9 vertices and 13 edges. What is the sum of all vertex degrees?

13

18

22

26

Handshake lemma → total degree = (2×13 = 26).

Explanation

Handshake lemma → total degree = (2×13 = 26).

4) In a directed graph, the (total) degree of a vertex is the sum of its in-degree and out-degree.

True

False

Total degree = indegree + outdegree.

Explanation

Total degree = indegree + outdegree.

5) A directed graph has 7 vertices and 20 directed edges (arcs). The sum of all in-degrees equals:

7

14

20

40

Every arc adds exactly 1 to some vertex’s in-degree.

Explanation

Every arc adds exactly 1 to some vertex’s in-degree.

6) A 4-regular simple graph has 7 vertices. How many edges does it have?

7

12

14

28

Total degree = (7×4 = 28); edges = (28/2 = 14).

Explanation

Total degree = (7×4 = 28); edges = (28/2 = 14).

7) Can a finite undirected graph have exactly three vertices of odd degree?

Yes

No

Odd-degree vertices must come in pairs.

Explanation

Odd-degree vertices must come in pairs.

8) If a connected graph has exactly two vertices of odd degree, then it has an Eulerian trail.

True

False

Eulerian trail criterion: exactly 0 or 2 odd vertices.

Explanation

Eulerian trail criterion: exactly 0 or 2 odd vertices.

9) A tree with 8 vertices has vertex degrees 3,3,2,2,1,1,1,1. How many leaves?

2

3

4

5

Leaves = vertices of degree 1 → four.

Explanation

Leaves = vertices of degree 1 → four.

10) In a simple graph with n vertices and m edges, the average degree is:

M/n

N/m

2m/n

M/2n

Total degree = (2m); average = (2m)/n.

Explanation

Total degree = (2m); average = (2m)/n.

11) Can there exist a 3-regular simple graph on 7 vertices?

Yes

No

Total degree = 21, odd → impossible.

Explanation

Total degree = 21, odd → impossible.

12) In any bipartite graph, the sum of the degrees on the left equals the sum on the right.

True

False

Each edge contributes 1 degree to each side.

Explanation

Each edge contributes 1 degree to each side.

13) Which degree sequence cannot be the degree sequence of a simple graph on 5 vertices?

3,3,2,2,2

4,3,2,1,0

2,2,2,2,2

4,4,1,1,0

Fails graphicality constraints.

Explanation

Fails graphicality constraints.

14) A graph on n vertices has one vertex of degree (n-1) and all others degree 1. What standard graph is this?

Path graph (P_n)

Complete graph (K_n)

Star graph (K_{1,n-1})

Cycle graph (C_n)

One center (degree n−1), others leaves (degree 1).

Explanation

One center (degree n−1), others leaves (degree 1).

15) Consider the path graph P5. What is its degree sequence (sorted)?

1,1,1,1,1

1,2,2,2,1

2,2,2,2,2

0,1,2,2,3

Endpoints degree 1; internal degree 2.

Explanation

Endpoints degree 1; internal degree 2.