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.

Question

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

Accepted Answer

11 &le; e &le; 66 — For a given triangle, any point can have 2 edges. A graph with 12 points will have 12 &minus; 1 = 11 edges at least as shown. The maximum number of edges will occur when each point is connected to all the others. &there4; The first point will form 11 edges, the second will form 10 edges, the third will form 9 edges and so on. &there4; The maximum number of edges = 11 + 10 + 9 + &hellip; + 1 = 66 &there4; 11 &le; e &le; 66 Hence, option (a). Alternatively, The maximum number of edges joining 12 p

CAT 2003 Slot 1 — QA Question 48

Answer & solution

Related Permutation & Combination questions