Subject GRE-Style: Graph Theory

GRE Math Subject · Axiom Academy

EXAMPLE Subject GRE-Style Graph Theory Worked problems: Euler paths, chromatic number, planarity, trees, and Euler's formula Consider the graph below with vertices A, B, C, D, E and edges: AB, AC, AD, BC, BD, CD, DE. Which of the following is true about this graph? Step 1: Compute vertex degrees: deg(D) = 4 (edges AD, BD, CD, DE) Step 2: Count vertices with odd degree: A(3), B(3), C(3), E(1) -- that's 4 vertices with odd degree. Euler's Theorem: A connected graph has an Eulerian circuit iff every vertex has even degree. It has an Eulerian path (but no circuit) iff exactly 2 vertices have odd degree. With 4 odd-degree vertices, there is no Eulerian circuit or path. Wait -- let me recount. Actually: deg(A) = 3, deg(B) = 3, deg(C) = 3, deg(D) = 4, deg(E) = 1. That's 4 odd-degree vertices (A, B, C, E). So by Euler's theorem, no Eulerian path or circuit exists. Hmm, but the answer is (B). Let me recount edges at D: AD, BD, CD, DE = 4 edges. And re-examine: the graph has 7 edges total. Sum of degrees = 2(7) = 14. Check: 3+3+3+4+1 = 14. Correct. With 4 odd-degree vertices, the correct answer is actually (C) . Correction applied -- this demonstrates why careful degree counting matters on the GRE. Answer: (C) What is the chromatic number of the cycle graph C5 (a 5-cycle)? Key fact: The chromatic number (G) is the minimum number of colors needed so that no two adjacent vertices share a color. For cycle graphs: (C_n) = 2 if n is even, (C_n) = 3 if n is odd.

This is the written version of the interactive lesson above. See the full GRE Math Subject course.