CPS 420 W2017 MIDTERM 1 SOLUTIONS 1 PART A – GRAPH THEORY – 30 MARKS
1. Equivalent Graphs (4 marks)
Label the vertices from A to H and edges from 1 to 11 of the graph on the right to show that it is equivalent to the graph on the left.
If we redraw the graph on the left slightly to line up vertices A, E, H, C, we get the graph on the right
BB
A
23
C
23
F 11 G
1 10 7 4
AEHC 6985
14 11
F
10
G
7
EH 65
98
D
D
D
You can see that the graph is symmetric along the axis formed by B and D. You can also see the the subgraph FAED is symmetric along the axix formed by F and D, and the subgraph GHCD is symmetric along the axis formed by G and D.
Therefore there will be four solutions, all of which with B and D in the same location, as shown on the diagram to the right.
2. Graph Degrees (6 marks)
B
ForG
ForG
For each of the following questions, either draw a graph with the requested properties, or explain convincingly (possibly by quoting a theorem) why such a graph cannot be drawn.
a) A graph with 5 vertices of degrees 5, 5, 4, 4, 3
The total degree of this graph would be 21. However, according to the handshake theorem, the total degree of a graph must be even. Therefore it is not possible to draw such a graph.
b) A graph with 5 vertices of degrees 5, 5, 4, 4, 4
This graph, on the other hand is possible because it has a total degree of 22 which is even. There are many different solutions.
CPS 420 W2017 MIDTERM 1 SOLUTIONS 2
3. Acquaintance Graphs (8 marks)
Suppose that in a group of 6 people A, B, C, D, E, and F the following pairs of people are acquainted with each other: A and B, B and D, A and D, A and F, C and D, C and E, C and F.
a)
Draw a graph G to represent who is acquainted with whom
A
FB ECEC
DD
What is G ∪ H? This is K6, the complete graph with 6 vertices.
Connected Components (8 marks)
b) Draw a graph H to represent who is not acquainted with whom
A
FB
4.
c)
This question and the next one are based on this graph:
A1BC8DE 10
9
3
2 7 12
5 4
5.
a)
b)
I
6 11
FGH J
An edge of a graph whose removal disconnects the graph of which it is a part is called a “bridge”. List all the bridges of the graph above.
4, 8, 9
If you were to remove all the bridges that you listed in part a) from the graph, how many connected components would this graph have? List them.
There would be 4 connected components corresponding to the following sets of vertices {A,B,F}, {D}, {I}, and {C,G,H,E,J}
Walks (4 marks)
For each of the 4 walks in the graph in question 4, Indicate with True of False in the table below whether the walks in the graph in question 4 have each of the properties
Walk: A1B3F2A4G H6G5C7H11J12E10H C8D8C7H6G5C I9D8C5G4A
Path/Trail
T
T
F
T
(Simple) path
F
F
F
T
Closed walk
F
T
T
F
Circuit
F
T
F
F
Simple circuit
F
F
F
F
CPS 420 W2017 MIDTERM 1 SOLUTIONS 3
PART B – SEQUENCES AND RECURRENCE RELATIONS – 10 MARKS
Given the sequence an defined with the recurrence relation:
a1 = 1
an = an-1 + n + 1 for n>1
1. Terms of a Sequence (5 marks)
Calculate a2, a3, a4, a5, a6
Keep your intermediate answers as you will need them in the next question.
a2 = a1+2+1 = 1+2+1 = 4
a3 = a2+3+1 = 1+2+1+3+1 = 1+2+3+2 = 8
a4 = a3+4+1 = 1+2+1+3+1+4+1 = 1+2+3+4+3 = 13
a5 = a4+5+1 = 1+2+1+3+1+4+1+5+1 = 1+2+3+4+5+4 = 19
a6 = a5+6+1 = 1+2+1+3+1+4+1+5+1+6+1 1+2+3+4+5+6+5 = 264
2. Iteration (5 marks)
Using iteration, solve the recurrence relation when n1 (i.e. find an analytic formula for an). Simplify your answer as much as possible, showing your work. In particular, your final answer should not contain sums and products.
Based on the pattern above, when n>1 an=∑𝑛𝑖=1𝑖+𝑛−1=𝑛(𝑛+1)+𝑛−1= 𝑛(𝑛+1)+2(𝑛−1)=𝑛2+3𝑛−2
222
substituting for n=1, the formula becomes 12+3−2 = 2/2 = 1, so this formula also works when
n=1
2
CPS 420 W2017 MIDTERM 1 SOLUTIONS 4
PART C – INDUCTION – 20 MARKS
Prove by induction that for all positive integers n, ∑𝑛𝑖=2 𝑖(𝑖 − 1) = 𝑛(𝑛−1)(𝑛+1)
3
No other method is acceptable.
Be sure to lay out your proof clearly and correctly and to justify every step.
Let P(n) be the property ∑𝑛𝑖=2 𝑖(𝑖 − 1) = 𝑛(𝑛−1)(𝑛+1) 3
We must prove ∀n∈N+ P(n) Proof:
Basic Step: n=1
∑𝑛𝑖=2 𝑖(𝑖 − 1) = ∑1𝑖=2 𝑖(𝑖 − 1) = 0 because 1<2 so the sum has no terms
𝑛(𝑛−1)(𝑛+1) = 1×0×2 = 0 33
Therefore P(1) is true
Inductive step:
Assume that P(k) is true for some positive integer k,
i.e , ∑𝑘𝑖=2 𝑖(𝑖 − 1) = 𝑘(𝑘−1)(𝑘+1) (inductive hypothesis) 3
We must show that P(k+1) is also true,
i.e. we must show that ∑𝑘+1 𝑖(𝑖 − 1) = (𝑘+1)(𝑘+1−1)(𝑘+1+1)
𝑖=2 3 i.e. we must show that ∑𝑘+1 𝑖(𝑖 − 1) = (𝑘+1)(𝑘)(𝑘+2)
∑𝑘+1 𝑖(𝑖 − 1) 𝑖=2
= ( 𝑘 + 1 ) 𝑘 + ∑ 𝑘𝑖 = 2 𝑖 ( 𝑖 − 1 )
= (k+1)k + 𝑘(𝑘−1)(𝑘+1) 3
= k(k+1)(1+𝑘−1) 3
= k(k+1)(3+𝑘−1) 3
= (𝑘+1)(𝑘)(𝑘+2) 3
𝑖=2
3
Taking the leading term out of the sum by inductive hypothesis
factoring k(k+1) algebra
algebra
QED