Advanced Vertex Degrees and Graph Properties 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 loops at (v)

The number of paths starting at (v)

In a simple graph, the degree equals the number of vertices adjacent to (v).

Explanation

In a simple graph, the degree equals the number of vertices adjacent to (v).

2) In an undirected graph with 8 vertices and 11 edges, what is the sum of all vertex degrees?

11

16

22

44

Handshake lemma: total degree = 2×11 = 22.

Explanation

Handshake lemma: total degree = 2×11 = 22.

3) A graph has 6 vertices with degrees 3,3,2,2,2,2. How many edges does it have?

7

8

9

10

Sum of degrees = 14 → edges = 14/2 = 7.

Explanation

Sum of degrees = 14 → edges = 14/2 = 7.

4) In any simple graph on (n) vertices, the degree of each vertex is at most (n-1).

True

False

A vertex cannot connect to itself, so max degree is (n−1).

Explanation

A vertex cannot connect to itself, so max degree is (n−1).

5) In the complete graph (K_7), what is the sum of degrees of all vertices?

21

42

56

84

Each vertex has degree 6 → total 42.

Explanation

Each vertex has degree 6 → total 42.

6) In a directed graph, the sum of all in-degrees equals:

The number of vertices

The number of edges

Twice the number of edges

Zero

Each directed edge contributes 1 to in-degree.

Explanation

Each directed edge contributes 1 to in-degree.

7) A vertex is pendant iff degree is:

0

1

2

≥3

Pendant means degree 1.

Explanation

Pendant means degree 1.

8) A graph is k-regular if every vertex has degree k.

True

False

Regular graphs have uniform degree.

Explanation

Regular graphs have uniform degree.

9) Which degree sequence cannot occur in a simple graph on 4 vertices?

3,3,3,3

2,2,2,2

1,1,2,2

0,1,2,3

Degree 3 forces all vertices connected → none can have degree 0.

Explanation

Degree 3 forces all vertices connected → none can have degree 0.

10) Star graph K1,n: degree of each leaf?

0

1

2

N

Leaves connect only to center.

Explanation

Leaves connect only to center.

11) Multigraph: v has 3 loops, 2 edges. deg(v)?

5

7

8

9

Loops are 2 each: 6+2=8.

Explanation

Loops are 2 each: 6+2=8.

12) Odd-degree vertices count is always even.

True

False

Handshake lemma yields even total degree.

Explanation

Handshake lemma yields even total degree.

13) Simple graph with degrees 4,4,4,4,4: number of vertices?

4

5

8

10

Degree 4 requires ≥5 vertices.

Explanation

Degree 4 requires ≥5 vertices.

14) Simple graph 10 vertices, one vertex deg 3: max edges?

37

38

39

40

Remaining 9 form 36 edges +3 =39.

Explanation

Remaining 9 form 36 edges +3 =39.

15) In simple graph on n vertices, at least two vertices share a degree.

True

False

Pigeonhole principle.

Explanation

Pigeonhole principle.