An ordered n-tuple (d_1, d_2, ..., d_n) with d_1 >= d_2 >= ... >= d_n is called graphic if there exists a simple undirected graph with n vertices having degrees d_1, d_2, ..., d_n respectively. Which one of the following 6-tuples is NOT graphic? A. (1, 1, 1, 1, 1, 1) B. (2, 2, 2, 2, 2, 2) C. (3, 3, 3, 1, 0, 0) D. (3, 2, 1, 1, 1, 0)

GATE 2014 · Discrete Mathematics · Degree of Graph · medium

Answer: C. (3, 3, 3, 1, 0, 0)

1. Check the easy ones first: A = (1,1,1,1,1,1) is three disjoint edges, graphic. B = (2,2,2,2,2,2) is a 6-cycle, graphic. D = (3,2,1,1,1,0) reduces (3,2,1,1,1) -> (1,0,0,1) -> sortable to all zeros, graphic.
2. Reduce tuple C: Drop the leading 3 and subtract 1 from the next three entries (3,3,1): they become (2,2,0), giving (2,2,0,0,0). Drop a 2 and subtract 1 from the next two (2,0): they become (1,-1). A degree of -1 is impossible.
3. Conclude: Only C fails the realisability test, so the answer is C.