BREAKING: Target Test Prep releases Brand New 2026 On Demand GMAT prep course

Redeem

Graph

Expert replies
by Aman verma » Sat Feb 27, 2010 11:38 am
Q: 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 :

a) 11<=e<=66

b)11<=e<=65

c)10<=e<=66

d)10<=e<=65

e)0<=e<=11



Note: The symbol<= mean less than or equal to.
800. Arjun's-Bird-Eye
Join the discussion
Source: — Problem Solving |

by firdaus117 » Sat Feb 27, 2010 12:08 pm
Minimum edges possible:
All points are in a line.
In this case,no of edges possible=11
Maximum edges possible:
All 12 points are connected to each other.
In this case total number of edges=11+10+9+8+7+6+5+4+3+2+1=66
Hence,option A
Join the discussion

by kstv » Sat Feb 27, 2010 7:20 pm
with 3 pts the min no of edges is 2 (3-1), this will form an angle but not a triangle.
the maximum no is 3 or 3c2 , which will form a triangle.
with 12 it will be (12-1) and 12c2 = 11<=e<=66
Join the discussion

by Aman verma » Sun Feb 28, 2010 3:08 am
Sol: The least number of edges will be when 11 points will be connected to a single point through the edges.Hence this combination will give us lest possible 11 edges.The maximum number of edges will be when all the 12 points are non-collinear and connected with each other.Hence the maximum number of edges = 12C2= 66.Ans[spoiler]a)[/spoiler]
800. Arjun's-Bird-Eye
Join the discussion