Question:
Consider a simple undirected graph of 10 vertices. If the graph is disconnected, then the maximum number of edges it can have is
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
In a disconnected graph, the maximum number of edges is achieved when the graph is a forest, i.e., a collection of trees.
Updated On: Jan 30, 2026
Hide Solution
Verified By Collegedunia
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.
Was this answer helpful?
0
0
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
- With respect to a TCP connection between a client and a server, which of the following is true?
- GATE CS - 2026
- Computer Networks
- Let $P, Q, R, S$ be relational schemas. Let ``$\rightarrow$'' indicate a functional dependency (FD) in this context. Which of the following best describes the meaning of a functional dependency?
- GATE CS - 2026
- Database Management Systems
- Let a Non-deterministic Finite Automaton (NFA) have 6 states over a finite alphabet. Which of the following cannot be the number of states in a minimal Deterministic Finite Automaton (DFA) that is equivalent to this NFA?
- GATE CS - 2026
- Theory of Computations
- A certain processor uses a fully associative cache of size 16 kB. The cache block size is 16 bytes. Assume that the main memory is byte addressable and uses a 32-bit address. How many bits are required for the Tag and the Index fields respectively in the addresses generated by the processor?
- GATE CS - 2026
- Computer Organization and Architecture
- Consider $Z = X - Y$, where $X$, $Y$ and $Z$ are all in sign-magnitude form. $X$ and $Y$ are each represented in $n$ bits. To avoid overflow, the representation of $Z$ would require a minimum of:
- GATE CS - 2026
- Computer Organization and Architecture
View More Questions