Question 8 - A-Level Maths

AQA D1 2010 June — Question 8 4 marks

Exam Board	AQA
Module	D1 (Decision Mathematics 1)
Year	2010
Session	June
Marks	4
Paper	Download PDF ↗
Mark scheme	Download PDF ↗
Topic	Graph Theory Fundamentals
Type	Finding variable values in degree sequences
Difficulty	Moderate -0.8 Part (a) is straightforward recall of basic graph theory (degree ranges from 0 to n-1). Part (b) requires applying the handshaking lemma (sum of degrees is even and equals 2×edges) to solve for x, which is a standard textbook exercise with minimal problem-solving demand. The algebraic manipulation is simple, making this easier than average.
Spec	7.02b Graph terminology: tree, simple, connected, simply connected 7.02d Complete graphs: K_n and number of arcs

A simple connected graph has six vertices.

One vertex has degree $x$. State the greatest and least possible values of $x$. [2 marks]
The six vertices have degrees $$x - 2, \quad x - 2, \quad x, \quad 2x - 4, \quad 2x - 4, \quad 4x - 12$$ Find the value of $x$, justifying your answer. [2 marks]

Show mark scheme Show mark scheme source

Question 8:

8

TOTAL

Answer all questions in the spaces provided.

1 (a) Draw a bipartite graph representing the following adjacency matrix.

1 2 3 4 5

A 1 0 0 0 1

B 0 1 1 1 0

C 0 1 1 1 0

D 1 0 0 0 1

E 1 0 0 0 1

(2 marks)

(b) If A, B, C, D and E represent five people and 1, 2, 3, 4 and 5 represent five tasks to

which they are to be assigned, explain why a complete matching is impossible.

(2 marks)

QUESTION

PART

REFERENCE

..........

Answer	Marks
..........	.......................................................................................................................................................

.......................................................................................................................................................

Answer	Marks	Guidance
1	2	3
A	1	0
B	0	1
C	0	1
D	1	0
E	1	0

QUESTION

PART

REFERENCE

..........

Answer	Marks
..........	.......................................................................................................................................................

.......................................................................................................................................................

2 (a) (i) Use a bubble sort to rearrange the following numbers into ascending order, showing

the list of numbers after each pass.

6 2 3 5 4 (3 marks)

(ii) Write down the number of comparisons on the first pass. (1 mark)

(b)(i) Use a shuttle sort to rearrange the following numbers into ascending order, showing

the list of numbers after each pass.

6 2 3 5 4 (4 marks)

(ii) Write down the number of comparisons on the first pass. (1 mark)

QUESTION

PART

REFERENCE

..........

Answer	Marks
..........	.......................................................................................................................................................

.......................................................................................................................................................

QUESTION

PART

REFERENCE

..........

Answer	Marks
..........	.......................................................................................................................................................

.......................................................................................................................................................

3 The network shows 10 towns. The times, in minutes, to travel between pairs of

towns are indicated on the edges.

A 12 B 27 C

21 22 17 16 21 14

E F

D G

8 18 22

20 11

20 19

H 6 I

25 26

10 9

J

(a) Use Kruskal’s algorithm, showing the order in which you select the edges, to find a

minimum spanning tree for the 10 towns. (6 marks)

(b) State the length of your minimum spanning tree. (1 mark)

(c) Draw your minimum spanning tree. (3 marks)

(d) If Prim’s algorithm, starting at B, had been used to find the minimum spanning tree,

state which edge would have been the final edge to complete the minimum spanning

tree. (1 mark)

QUESTION

PART

REFERENCE

..........

Answer	Marks
..........	.......................................................................................................................................................

.......................................................................................................................................................

QUESTION

PART

REFERENCE

..........

Answer	Marks
..........	.......................................................................................................................................................

.......................................................................................................................................................

4 The network below shows 13 towns. The times, in minutes, to travel between pairs

of towns are indicated on the edges.

The total of all the times is 384 minutes.

(a) Use Dijkstra’s algorithm on the network below, starting from M, to find the

minimum time to travel from M to each of the other towns. (7 marks)

(b)(i) Find the travelling time of an optimum Chinese postman route around the network,

starting and finishing at M. (6 marks)

(ii) State the number of times that the vertex F would appear in a corresponding route.

(1 mark)

QUESTION

PART

REFERENCE

Answer	Marks
(a)	B

12 A 13 D 11 C

19 19

7 6 10

F

E

G

20 20

11 13

22 H

I

9 40 8 40

15 11

J 5 K 6 L

6 12 9

M

QUESTION

PART

REFERENCE

..........

Answer	Marks
..........	.......................................................................................................................................................

.......................................................................................................................................................

5 Phil, a squash coach, wishes to buy some equipment for his club. In a town centre,

there are six shops, G, I, N, R, S and T, that sell the equipment.

The time, in seconds, to walk between each pair of shops is shown in the table.

Phil intends to check prices by visiting each of the six shops before returning to his

starting point.

G I N R S T

G – 81 82 86 72 76

I 81 – 80 82 68 73

N 82 80 – 84 70 74

R 86 82 84 – 74 70

S 72 68 70 74 – 64

T 76 73 74 70 64 –

(a) Use the nearest neighbour algorithm starting from S to find an upper bound for Phil’s

minimum walking time. (4 marks)

(b) Write down a tour starting from N which has a total walking time equal to your

answer to part (a). (1 mark)

(c) By deleting S, find a lower bound for Phil’s minimum walking time. (5 marks)

QUESTION

PART

REFERENCE

..........

Answer	Marks
..........	.......................................................................................................................................................

.......................................................................................................................................................

Answer	Marks	Guidance
G	I	N
G	–	81
I	81	–
N	82	80
R	86	82
S	72	68
T	76	73

QUESTION

PART

REFERENCE

..........

Answer	Marks
..........	.......................................................................................................................................................

.......................................................................................................................................................

6 Phil is to buy some squash balls for his club. There are three different types of ball

that he can buy: slow, medium and fast.

He must buy at least 190 slow balls, at least 50 medium balls and at least 50 fast

balls.

He must buy at least 300 balls in total.

Each slow ball costs £2.50, each medium ball costs £2.00 and each fast ball costs

£2.00.

He must spend no more than £1000 in total.

At least 60% of the balls that he buys must be slow balls.

Phil buys x slow balls, y medium balls and z fast balls.

(a) Find six inequalities that model Phil’s situation. (4 marks)

(b) Phil decides to buy the same number of medium balls as fast balls.

(i) Show that the inequalities found in part (a) simplify to give

1 x5190, y550, xþ2y5300, 5xþ8y42000, y4 x (2 marks)

3 (ii) Phil sells all the balls that he buys to members of the club. He sells each slow ball

for £3.00, each medium ball for £2.25 and each fast ball for £2.25. He wishes to

maximise his profit.

On Figure 1 on page 14, draw a diagram to enable this problem to be solved

graphically, indicating the feasible region and the direction of an objective line.

(7 marks)

(iii) Find Phil’s maximum possible profit and state the number of each type of ball that

he must buy to obtain this maximum profit. (4 marks)

QUESTION

PART

REFERENCE

..........

Answer	Marks
..........	.......................................................................................................................................................

.......................................................................................................................................................

QUESTION

PART

REFERENCE

..........

Answer	Marks
..........	.......................................................................................................................................................

.......................................................................................................................................................

QUESTION

PART

REFERENCE

Answer	Marks
(b)(ii)	Figure 1

~ x

– 054

– 004

x – 053

1 3

4y

,00024y8þx5

– 003

– 052

,0035y2þx

– 002

,055y

– 051

,0915x

– 001

– 05

~ –003 –052 –002 –051 –001 –05 –0 – 0

y

~

QUESTION

PART

REFERENCE

..........

Answer	Marks
..........	.......................................................................................................................................................

.......................................................................................................................................................

7 A student is testing a numerical method for finding an approximation for p.

The algorithm that the student is using is as follows.

Line 10 Input A, B, C, D, E

Line 20 Let A ¼ Aþ2

Line 30 Let B ¼ (cid:1)B

B

Line 40 Let C ¼

A

Line 50 Let D ¼ DþC

2 Line 60 Let E ¼ ðD(cid:1)3:14Þ

Line 70 If E < 0:05 then go to Line 90

Line 80 Go to Line 20

Line 90 Print ‘p is approximately’, D

Line 100 End

Trace the algorithm in the case where the input values are

A ¼ 1, B ¼ 4, C ¼ 0, D ¼ 4, E ¼ 0 (6 marks)

QUESTION

PART

REFERENCE

..........

Answer	Marks
..........	.......................................................................................................................................................

.......................................................................................................................................................

QUESTION

PART

REFERENCE

..........

Answer	Marks
..........	.......................................................................................................................................................

.......................................................................................................................................................

8 A simple connected graph has six vertices.

(a) One vertex has degree x. State the greatest and least possible values of x. (2 marks)

(b) The six vertices have degrees

x(cid:1)2, x(cid:1)2, x, 2x(cid:1)4, 2x(cid:1)4, 4x(cid:1)12

Find the value of x, justifying your answer. (2 marks)

QUESTION

PART

REFERENCE

..........

Answer	Marks
..........	.......................................................................................................................................................

.......................................................................................................................................................

QUESTION

PART

REFERENCE

..........

Answer	Marks
..........	.......................................................................................................................................................

.......................................................................................................................................................

PMT

Donotwrite

20 outsidethe

box

QUESTION

PART

REFERENCE

.................................................................................................................................................................

END OF QUESTIONS

Copyright(cid:1)2010AQAanditslicensors. Allrightsreserved.

(20)

P28322/Jun10/MD01

Question 8:
8
TOTAL
Answer all questions in the spaces provided.
1 (a) Draw a bipartite graph representing the following adjacency matrix.
1 2 3 4 5
A 1 0 0 0 1
B 0 1 1 1 0
C 0 1 1 1 0
D 1 0 0 0 1
E 1 0 0 0 1
(2 marks)
(b) If A, B, C, D and E represent five people and 1, 2, 3, 4 and 5 represent five tasks to
which they are to be assigned, explain why a complete matching is impossible.
(2 marks)
QUESTION
PART
REFERENCE
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
.......... | .......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
1 | 2 | 3 | 4 | 5
A | 1 | 0 | 0 | 0 | 1
B | 0 | 1 | 1 | 1 | 0
C | 0 | 1 | 1 | 1 | 0
D | 1 | 0 | 0 | 0 | 1
E | 1 | 0 | 0 | 0 | 1
QUESTION
PART
REFERENCE
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
.......... | .......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
2 (a) (i) Use a bubble sort to rearrange the following numbers into ascending order, showing
the list of numbers after each pass.
6 2 3 5 4 (3 marks)
(ii) Write down the number of comparisons on the first pass. (1 mark)
(b)(i) Use a shuttle sort to rearrange the following numbers into ascending order, showing
the list of numbers after each pass.
6 2 3 5 4 (4 marks)
(ii) Write down the number of comparisons on the first pass. (1 mark)
QUESTION
PART
REFERENCE
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
.......... | .......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
QUESTION
PART
REFERENCE
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
.......... | .......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
3 The network shows 10 towns. The times, in minutes, to travel between pairs of
towns are indicated on the edges.
A 12 B 27 C
21 22 17 16 21 14
E F
D G
8 18 22
20 11
20 19
H 6 I
25 26
10 9
J
(a) Use Kruskal’s algorithm, showing the order in which you select the edges, to find a
minimum spanning tree for the 10 towns. (6 marks)
(b) State the length of your minimum spanning tree. (1 mark)
(c) Draw your minimum spanning tree. (3 marks)
(d) If Prim’s algorithm, starting at B, had been used to find the minimum spanning tree,
state which edge would have been the final edge to complete the minimum spanning
tree. (1 mark)
QUESTION
PART
REFERENCE
..........
..........
..........
.......... | .......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
QUESTION
PART
REFERENCE
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
.......... | .......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
4 The network below shows 13 towns. The times, in minutes, to travel between pairs
of towns are indicated on the edges.
The total of all the times is 384 minutes.
(a) Use Dijkstra’s algorithm on the network below, starting from M, to find the
minimum time to travel from M to each of the other towns. (7 marks)
(b)(i) Find the travelling time of an optimum Chinese postman route around the network,
starting and finishing at M. (6 marks)
(ii) State the number of times that the vertex F would appear in a corresponding route.
(1 mark)
QUESTION
PART
REFERENCE
(a) | B
12
A 13 D 11 C
19 19
7 6 10
F
E
G
20 20
20 20
11 13
22
H
I
9
40 8 40
15 11
J 5 K 6 L
6 12 9
M
QUESTION
PART
REFERENCE
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
.......... | .......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
5 Phil, a squash coach, wishes to buy some equipment for his club. In a town centre,
there are six shops, G, I, N, R, S and T, that sell the equipment.
The time, in seconds, to walk between each pair of shops is shown in the table.
Phil intends to check prices by visiting each of the six shops before returning to his
starting point.
G I N R S T
G – 81 82 86 72 76
I 81 – 80 82 68 73
N 82 80 – 84 70 74
R 86 82 84 – 74 70
S 72 68 70 74 – 64
T 76 73 74 70 64 –
(a) Use the nearest neighbour algorithm starting from S to find an upper bound for Phil’s
minimum walking time. (4 marks)
(b) Write down a tour starting from N which has a total walking time equal to your
answer to part (a). (1 mark)
(c) By deleting S, find a lower bound for Phil’s minimum walking time. (5 marks)
QUESTION
PART
REFERENCE
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
.......... | .......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
G | I | N | R | S | T
G | – | 81 | 82 | 86 | 72 | 76
I | 81 | – | 80 | 82 | 68 | 73
N | 82 | 80 | – | 84 | 70 | 74
R | 86 | 82 | 84 | – | 74 | 70
S | 72 | 68 | 70 | 74 | – | 64
T | 76 | 73 | 74 | 70 | 64 | –
QUESTION
PART
REFERENCE
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
.......... | .......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
6 Phil is to buy some squash balls for his club. There are three different types of ball
that he can buy: slow, medium and fast.
He must buy at least 190 slow balls, at least 50 medium balls and at least 50 fast
balls.
He must buy at least 300 balls in total.
Each slow ball costs £2.50, each medium ball costs £2.00 and each fast ball costs
£2.00.
He must spend no more than £1000 in total.
At least 60% of the balls that he buys must be slow balls.
Phil buys x slow balls, y medium balls and z fast balls.
(a) Find six inequalities that model Phil’s situation. (4 marks)
(b) Phil decides to buy the same number of medium balls as fast balls.
(i) Show that the inequalities found in part (a) simplify to give
1
x5190, y550, xþ2y5300, 5xþ8y42000, y4 x (2 marks)
3
(ii) Phil sells all the balls that he buys to members of the club. He sells each slow ball
for £3.00, each medium ball for £2.25 and each fast ball for £2.25. He wishes to
maximise his profit.
On Figure 1 on page 14, draw a diagram to enable this problem to be solved
graphically, indicating the feasible region and the direction of an objective line.
(7 marks)
(iii) Find Phil’s maximum possible profit and state the number of each type of ball that
he must buy to obtain this maximum profit. (4 marks)
QUESTION
PART
REFERENCE
..........
..........
..........
..........
..........
..........
.......... | .......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
QUESTION
PART
REFERENCE
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
.......... | .......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
QUESTION
PART
REFERENCE
(b)(ii) | Figure 1
~ x
– 054
– 004
x – 053
1 3
4y
,00024y8þx5
– 003
– 052
,0035y2þx
– 002
,055y
– 051
,0915x
– 001
– 05
~ –003 –052 –002 –051 –001 –05 –0 – 0
y
~
~
QUESTION
PART
REFERENCE
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
.......... | .......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
7 A student is testing a numerical method for finding an approximation for p.
The algorithm that the student is using is as follows.
Line 10 Input A, B, C, D, E
Line 20 Let A ¼ Aþ2
Line 30 Let B ¼ (cid:1)B
B
Line 40 Let C ¼
A
Line 50 Let D ¼ DþC
2
Line 60 Let E ¼ ðD(cid:1)3:14Þ
Line 70 If E < 0:05 then go to Line 90
Line 80 Go to Line 20
Line 90 Print ‘p is approximately’, D
Line 100 End
Trace the algorithm in the case where the input values are
A ¼ 1, B ¼ 4, C ¼ 0, D ¼ 4, E ¼ 0 (6 marks)
QUESTION
PART
REFERENCE
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
.......... | .......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
QUESTION
PART
REFERENCE
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
.......... | .......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
8 A simple connected graph has six vertices.
(a) One vertex has degree x. State the greatest and least possible values of x. (2 marks)
(b) The six vertices have degrees
x(cid:1)2, x(cid:1)2, x, 2x(cid:1)4, 2x(cid:1)4, 4x(cid:1)12
Find the value of x, justifying your answer. (2 marks)
QUESTION
PART
REFERENCE
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
.......... | .......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
QUESTION
PART
REFERENCE
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
.......... | .......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
.......................................................................................................................................................
PMT
Donotwrite
20 outsidethe
box
QUESTION
PART
REFERENCE
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
END OF QUESTIONS
Copyright(cid:1)2010AQAanditslicensors. Allrightsreserved.
(20)
P28322/Jun10/MD01

Show LaTeX source

A simple connected graph has six vertices.

\begin{enumerate}[label=(\alph*)]
\item One vertex has degree $x$. State the greatest and least possible values of $x$. [2 marks]

\item The six vertices have degrees
$$x - 2, \quad x - 2, \quad x, \quad 2x - 4, \quad 2x - 4, \quad 4x - 12$$

Find the value of $x$, justifying your answer. [2 marks]
\end{enumerate}

\hfill \mbox{\textit{AQA D1 2010 Q8 [4]}}

This paper (8 questions)

View full paper

Q1 4 Q2 9 Q3 11 Q4 14 Q5 10 Q6 17 Q7 6 Q8 4