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:

  • All Quant CAT complete Formulas and shortcuts PDF
  • 35+ CAT previous year papers with video solutions PDF
  • 5000+ Topic-wise Previous year CAT Solved Questions for Free

cracku

Boost your Prep!

Download App