Questions: Introduction to Graph Theory

Question 1

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

• A. 8
• B. 16
• C. 6
• D. Cannot be determined without the edge list

Answer: (A)

By the handshaking lemma, the sum of all degrees equals twice the number of edges. Sum of degrees = 4+3+3+2+2+2 = 16, so the number of edges = 16/2 = 8. This works for any simple undirected graph — no edge list needed.

Question 2

Two drawings of a graph that look geometrically different (e.g., one has crossing edges, the other doesn't) should be different graphs.

• T. True
• F. False

Answer: False

A graph is defined by its vertex and edge sets G = (V, E), not by how it is drawn on paper. The same graph can be drawn in infinitely many ways. Two graphs that look different in a drawing may be isomorphic — structurally identical. Only the combinatorial relationships matter, not the geometric positions of vertices.

Question 3

What does the degree of a vertex represent, and why does the handshaking lemma follow from this definition?

Model answer: The degree of a vertex is the number of edges incident to it. The handshaking lemma (sum of degrees = 2|E|) follows because each edge contributes exactly 1 to the degree of each of its two endpoints, so every edge is counted exactly twice when you sum all degrees.

This question tests whether students understand degree as counting edge-endpoint incidences. The factor of 2 is not arbitrary — it reflects the fact that every edge has two endpoints. This is a clean example of a combinatorial identity that follows directly from the definition.