Question 95

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 point through a sequence of edges. The number of edges, e, in the graph must satisfy the condition

Solution

Take any 12 points.

The maximum number of edges which can be drawn through these 12 points are $$^{12}C_2$$ = 66

The minimum number of edges which can be drawn through these 12 points are 12-1 = 11 as the resulting figure need not be closed. It might be open.

Create a FREE account and get:

CAT Quant Questions | CAT Quantitative Ability