Questions: Graphs: Basic Concepts and Terminology

Question 1

An undirected graph has 5 vertices with degrees 2, 3, 3, 4, 4. How many edges does the graph have?

• A. 16 edges
• B. 8 edges
• C. 5 edges
• D. 14 edges

Answer: (B)

The handshaking lemma states that the sum of all vertex degrees equals 2|E|. Sum of degrees = 2 + 3 + 3 + 4 + 4 = 16. Therefore 2|E| = 16, so |E| = 8. Every edge contributes exactly 1 to each of its two endpoints' degree counts, so every edge is counted exactly twice in the total degree sum. The lemma also implies that the number of odd-degree vertices is always even — a useful constraint for checking whether a proposed degree sequence is realizable.

Question 2

In a directed graph, vertex v has in-degree 3 and out-degree 2. How many edges are incident to v in total?

• A. 2 edges — only outgoing edges are 'incident' to a vertex in a directed graph
• B. 3 edges — only incoming edges count because v is a destination
• C. 5 edges — both incoming and outgoing edges are incident to v
• D. 6 edges — in-degree and out-degree are multiplied

Answer: (C)

In a directed graph, a vertex's total edge count is in-degree + out-degree. Vertex v has 3 incoming edges and 2 outgoing edges, for 5 total incident edges. This is different from an undirected graph, where 'degree' is a single number; directed graphs require two separate counts. Common mistakes include counting only one direction (options A and B) or confusing degree with some product.

Question 3

In any undirected graph, the sum of all vertex degrees is always an even number.

• T. True
• F. False

Answer: True

This is the handshaking lemma: the sum of all vertex degrees = 2|E|, which is always even. The reason is that each edge {u, v} contributes exactly 1 to u's degree and exactly 1 to v's degree — contributing exactly 2 to the total degree sum. Summing over all edges gives 2|E|. A useful corollary follows: every undirected graph has an even number of odd-degree vertices (since odd terms must pair up to give an even total). This rules out many seemingly-possible degree sequences before attempting to construct a graph.

Question 4

A path in a graph is a sequence of vertices where consecutive vertices are connected by edges; a vertex may appear more than once as long as no edge is repeated.

• T. True
• F. False

Answer: False

By standard definition, a path requires that no vertex repeats (which also prevents edge repetition). A sequence allowing vertex repetition but no edge repetition is called a *trail*; a sequence allowing both is a *walk*. The distinction matters: Eulerian path theorems concern trails (traverse every edge exactly once); Hamiltonian path problems concern paths (visit every vertex exactly once). Using 'path' loosely to mean 'walk' causes errors in applying graph theorems.

Question 5

State the handshaking lemma and explain why it holds. What is one useful consequence of the lemma?

Model answer: Handshaking lemma: in any undirected graph G = (V, E), the sum of all vertex degrees equals 2|E|. It holds because each edge {u, v} contributes exactly 1 to deg(u) and exactly 1 to deg(v), so it contributes exactly 2 to the total degree sum. Summing over all |E| edges gives 2|E|. One useful consequence: every graph has an even number of odd-degree vertices. Since the total degree sum is even (= 2|E|), and the contribution of even-degree vertices is already even, the odd-degree vertices must contribute an even sum — requiring an even count of them.

The 'even number of odd-degree vertices' consequence is frequently used to prove impossibility: if a proposed graph requires an odd number of vertices with odd degree, it cannot exist. It also underlies the Euler path/circuit theorem: an Euler circuit exists iff all vertices have even degree, and an Euler path (not circuit) exists iff exactly two vertices have odd degree — both conclusions flow directly from degree counting.