In-Depth Degree Analysis in Graph Theory Quiz

1) 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).

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

Yes

No

Total degree = 21, odd → impossible.

Explanation

Total degree = 21, odd → impossible.

3) 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.

4) 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.

5) 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).

6) 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.

7) 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.

8) 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).

9) 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.

10) 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.

11) 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.

12) 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.

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 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).

15) 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.

In-Depth Degree Analysis in Graph Theory Quiz

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

2)

What first name or nickname would you like us to use?

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

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

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

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

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

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

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

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

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

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

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

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

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

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