Consider a simple undirected graph of 10 vertices. If the graph is disconnected, then the maximum number of edges it can have is
Show Hint
Correct Answer: 36
Solution and Explanation
To find the maximum number of edges in a disconnected graph, consider that removing the fewest number of edges while ensuring the graph remains disconnected is optimal. The simplest form of disconnection involves one component containing the maximum number of vertices possible without encompassing all vertices. Let one component have 9 vertices and the other 1 to ensure disconnection. The maximum number of edges in the 9-vertex component is given by: 9(9-1)/2=36.
No edges exist between the separate components.
Thus, the maximum number of edges ensuring the graph remains disconnected is 36.
Top GATE CS Engineering Mathematics Questions
- Let \( f(x) \) be a continuous function from \( \mathbb{R} \) to \( \mathbb{R} \) such that: \[ f(x) = 1 - f(2 - x) \] Which one of the following options is the CORRECT value of \( \int_0^2 f(x) \, dx \)?
- For a Boolean variable \(x\), which of the following statements is/are FALSE?}
- Consider 4-variable functions \(f_1, f_2, f_3, f_4\) expressed in sum-of-minterms form as given below. \[ f_1 = \Sigma(0,2,3,5,7,8,11,13)
f_2 = \Sigma(1,3,5,7,11,13,15)
f_3 = \Sigma(0,1,4,11)
f_4 = \Sigma(0,2,6,13) \] The circuit is represented as: \begin{center} \includegraphics[width=6cm]{50.png} \end{center} With respect to the circuit given above, which of the following options is/are CORRECT? In the diagram, the lines QR and ST are parallel to each other. The shortest distance between these two lines is half the shortest distance between the point P and the line QR. What is the ratio of the area of the triangle PST to the area of the trapezium SQRT?
Note: The figure shown is representative
- Consider the given system of linear equations for variables \(x\) and \(y\), where \(k\) is a real-valued constant. Which of the following option(s) is/are CORRECT? \[ x + ky = 1 \] \[ kx + y = -1 \]
Top GATE CS Questions
- Which of the following sequences when stored in an array at locations A[1],..., A[10] forms a max-heap?
- The Lucas sequence Ln is defined by the recurrence relation: Ln = Ln−1 + Ln−2, for n ≥ 3, with L1 = 1 and L2 = 3. Which one of the options given is TRUE?
- Which of the following fields of IP header is/are always modified by any router before it forwards to IP Packet ?
- Which one of the following CIDR profix exactly represent the range of IP addresses 10.12.2.0 to 10.12.3.255?
- Consider an ethernet segment whose transmission is \(10^8\) bits per second. Maximum segment length \(500\ m\), speed of the provocation media velocity is \(2 × 10^8\) meter per second. What is the minimum frame size in bits ?