CAT 2003 Slot 1 — QA Question 48
Each question is followed by two statements, A and B. Answer each question using the following instructions
Choose 1 if the question can be answered by using one of the statements alone but not by using the other statement alone.
Choose 2 if the question can be answered by using either of the statements alone.
Choose 3 if the question can be answered by using both statements together but not by either statement alone.
Choose 4 if the question cannot be answered on the basis of the two statements.
A graph may be defined as a set of points connected by lines called edges. Every edge connects a pair of points. Thus, a triangle is a graph with 3 edges and 3 points. The degree of a point is the number of edges connected to it. For example, a triangle is a graph with three points of degree 2 each. Consider a graph with 12 points. It is possible to reach any point from any other point through a sequence of edges. The number of edges, e, in the graph must satisfy the condition
Answer & solution
11 ≤ e ≤ 66
- B
10 ≤ e ≤ 66
- C
11 ≤ e ≤ 65
- D
0 ≤ e ≤ 11
For a given triangle, any point can have 2 edges.
A graph with 12 points will have 12 − 1 = 11 edges at least as shown.
The maximum number of edges will occur when each point is connected to all the others.
∴ The first point will form 11 edges, the second will form 10 edges, the third will form 9 edges and so on.
∴ The maximum number of edges = 11 + 10 + 9 + … + 1 = 66
∴ 11 ≤ e ≤ 66
Hence, option (a).
Alternatively,
The maximum number of edges joining 12 points to each other = 12C2 = 66
To go from each point to every other point, we need at least 11 edges.
∴ 11 ≤ e ≤ 66
Hence, option (a).