Mathematics Standard • Year 11 • Networks • Lesson 2
Degree Sequences · Master
Test degree-sequence claims and justify graph representations.
Practice
Unless a question says otherwise, treat each network as a simple undirected graph: edges are unordered vertex pairs, with no loops or duplicate edges. Show your reasoning in the answer space; an edge list is enough.
Q1 · Realise a sequence. Can a simple graph on four vertices have degree sequence (3,2,2,1)? Construct or explain one. 3 marks
Q2 · Build two representations. For V={A,B,C,D}, E={AB,AC,AD,BC}, give the degree sequence and neighbour list. 2 marks
Q3 · Spot an error. A student puts 1 in the C,C position of an adjacency matrix for a simple graph. What does this say, and why is it invalid? 2 marks
Q1 · Realise a sequence
Yes. Join a central vertex to all three others, then add an edge between two of those leaves. The degrees become (3,2,2,1).
Q2 · Build two representations
Degrees A=3,B=2,C=2,D=1, sequence (3,2,2,1). Neighbours: A:{B,C,D}; B:{A,C}; C:{A,B}; D:{A}.
Q3 · Spot an error
It represents a loop at C. A simple graph has no loops, so diagonal entries must be 0.