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 point through a sequence of edges. The number of edges, e, in the graph must satisfy the condition
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
Show Hint
Ask how few edges can still keep 12 points connected, and how many edges you get if every pair of points is joined once.
Updated On: Nov 7, 2026
- \( 11 \leq e \leq 66 \)
- \( 10 \leq e \leq 66 \)
- \( 11 \leq e \leq 65 \)
- \( 0 \leq e \leq 11 \)
Show Solution
Verified By Collegedunia
The Correct Option is A
Solution and Explanation
Step 1: Understand the setup:
A graph here is a set of points (12 of them) joined by edges. Every edge joins a pair of points. We take the usual meaning that two points are joined by at most one edge.
The graph is connected: from any point we can reach any other point through a chain of edges. We must find the range of the number of edges e.
Step 2: Find the smallest possible e:
Start with one point. To bring each of the other 11 points into the connected picture, we need at least one new edge for each of them.
So at least 11 edges are needed. With fewer than 11 edges, some point would be cut off from the rest and the graph would not be connected.
11 edges can really work: join the 12 points in a single chain (a path). That gives \(e = 11\), so the minimum is 11.
Step 3: Find the largest possible e:
Each edge uses up one pair of points, and a pair can have only one edge. The number of pairs from 12 points is
\[ \binom{12}{2} = \frac{12 \times 11}{2} = 66 \]
Joining every pair gives a connected graph with 66 edges, so the maximum is 66.
Step 4: Combine the two bounds:
So \(11 \le e \le 66\), and every value in between is possible (add edges to the chain one at a time).
Step 5: Why the other options are wrong:
Option 2 (\(10 \le e \le 66\)) allows 10 edges. With 10 edges, a connected graph on 12 points is not possible.
Option 3 (\(11 \le e \le 65\)) leaves out 66, but the complete graph with 66 edges is connected and allowed.
Option 4 (\(0 \le e \le 11\)) allows 0 edges, which cannot connect 12 points. It also stops at 11, but a connected graph on 12 points can have many more edges, up to 66.
Final Answer:
A connected graph on 12 points has at least 11 edges and at most 66 edges, so option 1 is correct. \[ \boxed{11 \le e \le 66 \; \text{(option 1)}} \]
A graph here is a set of points (12 of them) joined by edges. Every edge joins a pair of points. We take the usual meaning that two points are joined by at most one edge.
The graph is connected: from any point we can reach any other point through a chain of edges. We must find the range of the number of edges e.
Step 2: Find the smallest possible e:
Start with one point. To bring each of the other 11 points into the connected picture, we need at least one new edge for each of them.
So at least 11 edges are needed. With fewer than 11 edges, some point would be cut off from the rest and the graph would not be connected.
11 edges can really work: join the 12 points in a single chain (a path). That gives \(e = 11\), so the minimum is 11.
Step 3: Find the largest possible e:
Each edge uses up one pair of points, and a pair can have only one edge. The number of pairs from 12 points is
\[ \binom{12}{2} = \frac{12 \times 11}{2} = 66 \]
Joining every pair gives a connected graph with 66 edges, so the maximum is 66.
Step 4: Combine the two bounds:
So \(11 \le e \le 66\), and every value in between is possible (add edges to the chain one at a time).
Step 5: Why the other options are wrong:
Option 2 (\(10 \le e \le 66\)) allows 10 edges. With 10 edges, a connected graph on 12 points is not possible.
Option 3 (\(11 \le e \le 65\)) leaves out 66, but the complete graph with 66 edges is connected and allowed.
Option 4 (\(0 \le e \le 11\)) allows 0 edges, which cannot connect 12 points. It also stops at 11, but a connected graph on 12 points can have many more edges, up to 66.
Final Answer:
A connected graph on 12 points has at least 11 edges and at most 66 edges, so option 1 is correct. \[ \boxed{11 \le e \le 66 \; \text{(option 1)}} \]
Was this answer helpful?
0
0
Top CAT Quantitative Aptitude Questions
- In a triangle ABC,AB=AC=8cm. A circle drawn with BC as diameter passes through A. Another circle drawn with center at A passes through B and C. Then the area,in sq.cm,of the overlapping region between the two circles is
- The simple interest accrued on an amount of Rs.25,000 at the end of three years is Rs.7,500. What would be the compound interest accrued on the same amount at the same rate in the same period?
- What is the sum of all roots of the equation \(|x+4|^2–10|x+4|=24\)?
- A solid metal sphere is melted and smaller spheres of equal radii are formed. 10% of the volume of the sphere is lost in the process. The smaller spheres have a radius which is \(\frac{1}{9}\text{th}\) the larger sphere. If 10 litres of paint were needed to paint the larger sphere,how many litres are needed to paint all the smaller spheres?
- The ratio of the ages of a husband and his wife when they got married was 6:5. 4 years and 6 years after their marriage they had their 1st and 2nd children. The sum of the present ages of the husband and wife is 6.4 times the sum of the present ages of their children. The average age of the family at present is 18.5 years. Find the ratio of the ages of the husband and wife when their second child was born.
View More Questions
Top CAT Permutation and Combination Questions
- If among 200 students, 105 like pizza and 134 like burger, then the number of students who like only burger can possibly be
- In how many ways can 7 identical erasers be distributed among 4 kids in such a way that each kid gets at least one eraser but nobody gets more than 3 erasers?
In how many ways can 5 identical balls be distributed into 3 distinct boxes?
What is the value of x if:
2x · 3x+1 = 3888
In how many ways can 6 people be seated around a circular table?
View More Questions
Top CAT Questions
- Compare and contrast between Portia and Jessica characters in Merchant of Venice.
- In a triangle ABC,AB=AC=8cm. A circle drawn with BC as diameter passes through A. Another circle drawn with center at A passes through B and C. Then the area,in sq.cm,of the overlapping region between the two circles is
- The simple interest accrued on an amount of Rs.25,000 at the end of three years is Rs.7,500. What would be the compound interest accrued on the same amount at the same rate in the same period?
- What is the sum of all roots of the equation \(|x+4|^2–10|x+4|=24\)?
- A solid metal sphere is melted and smaller spheres of equal radii are formed. 10% of the volume of the sphere is lost in the process. The smaller spheres have a radius which is \(\frac{1}{9}\text{th}\) the larger sphere. If 10 litres of paint were needed to paint the larger sphere,how many litres are needed to paint all the smaller spheres?
View More Questions