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 Questions on Graph - Connectivity
The following simple undirected graph is referred to as the Peterson graph.
Which of the following statements is/are TRUE?
- GATE CS - 2022
- Engineering Mathematics
- Graph - Connectivity
- Let \( G(V, E) \) be a directed graph, where \( V = \{1, 2, 3, 4, 5\} \) is the set of vertices and \( E \) is the set of directed edges, as defined by the following adjacency matrix \( A \): \[ A[i][j] = \begin{cases} 1, & 1 \leq j \leq 5 \\ 0, & \text{otherwise} \end{cases} \] A[i][j] = 1 indicates a directed edge from node i to node j. A directed spanning tree of \( G \), rooted at \( r \in V \), is defined as a subgraph \( T \) of \( G \) such that the undirected version of \( T \) is a tree, and \( T \) contains a directed path from \( r \) to every other vertex in \( V \). The number of such directed spanning trees rooted at vertex 5 is
- GATE CS - 2022
- Engineering Mathematics
- Graph - Connectivity
- In an undirected connected planar graph \( G \), there are eight vertices and five faces. The number of edges in \( G \) is \(\underline{\hspace{2cm}}\).
- GATE CS - 2021
- Engineering Mathematics
- Graph - Connectivity
- Let $G=(V,E)$ be an undirected unweighted connected graph. The diameter of $G$ is defined as: \[ \text{diam}(G) = \max_{u,v \in V} \{\text{length of the shortest path between } u \text{ and } v\}. \] Let $M$ be the adjacency matrix of $G$. Define graph $G_2$ on the same set of vertices with adjacency matrix $N$, where \[ N_{ij} = \begin{cases} 1 & \text{if } M_{ij} > 0 \text{ or } P_{ij} > 0,\ \text{where } P=M^2,
0 & \text{otherwise}. \end{cases} \] Which one of the following statements is true?- GATE CS - 2021
- Engineering Mathematics
- Graph - Connectivity
Questions Asked in GATE CS exam
In a 4-bit ripple counter, if the period of the waveform at the last flip-flop is 64 microseconds, then the frequency of the ripple counter in kHz is ______________. {(Answer in integer)}
- GATE CS - 2025
- Flip-Flop
Consider the following C code segment:
int x = 126, y = 105; do { if (x > y) x = x - y; else y = y - x; } while (x != y); printf("%d", x);The output of the given C code segment is ____________. (Answer in integer)
- GATE CS - 2025
- Programming in C
The following two signed 2’s complement numbers (multiplicand \( M \) and multiplier \( Q \)) are being multiplied using Booth’s algorithm:
Multiplicand (\( M \)) Multiplier (\( Q \)) 1100 1101 1110 1101 1010 0100 1010 1010 The total number of addition and subtraction operations to be performed is __________. (Answer in integer)
- GATE CS - 2025
- Complementation
The maximum value of \(x\) such that the edge between the nodes B and C is included in every minimum spanning tree of the given graph is __________ (answer in integer).
- GATE CS - 2025
- Programming and Data Structures
Consider the following C program
The value printed by the given C program is __________ (Answer in integer).- GATE CS - 2025
- Programming in C