Graph

This topic has expert replies
Master | Next Rank: 500 Posts
Posts: 304
Joined: Wed Jan 27, 2010 8:35 am
Location: International Space Station
Thanked: 11 times
Followed by:3 members

Graph

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
Source: — Problem Solving |

User avatar
Master | Next Rank: 500 Posts
Posts: 102
Joined: Sat Feb 20, 2010 5:38 am
Location: IIM Ahmedabad
Thanked: 10 times

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

Legendary Member
Posts: 610
Joined: Fri Jan 15, 2010 12:33 am
Thanked: 47 times
Followed by:2 members

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

Master | Next Rank: 500 Posts
Posts: 304
Joined: Wed Jan 27, 2010 8:35 am
Location: International Space Station
Thanked: 11 times
Followed by:3 members

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