Official PYQ · 2002Q1.25Graphs: Connectivity, Matching, ColouringMCQ1 mark

GATE CS 2002 Q1.25 — Graphs: Connectivity, Matching, Colouring

The maximum number of edges in a $n$ -node undirected graph without self loops is

View worked solution

Answer: B

To find the maximum number of edges in an undirected graph with $n$ nodes and no self-loops, we consider the case of a complete graph ( $K_n$ ).

In a complete graph, every pair of distinct vertices is connected by exactly one edge. Since there are no self-loops, we do not have any edges connecting a vertex to itself.

The number of ways to choose a pair of distinct vertices from $n$ available vertices is given by the combination formula:

\binom{n}{2} = \frac{n(n-1)}{2}

Thus, the maximum number of edges in such a graph is $\frac{n(n-1)}{2}$ .

Correct Option: B

Free practice · Your answers on this page are not saved.

Published 10 Oct 2026

Report a correction

GATE CS · 2026Graphs: Connectivity, Matching, Colouring
Let $G(V, E)$ be a simple, undirected graph. A vertex cover of $G$ is a subset $V^{\prime} \subseteq V$ such that for every $(u, v) \in E, u \in V^{\prime}$ or $v \in V^{\prime}$ . Let the size of the smallest vertex cover in $G$ be $k$ . Let $S$ be any vertex cover of size $k$ . For a vertex $v \in V$ , which of the following constraints …
MCQ · 2 marks
GATE CS · 2026Graphs: Connectivity, Matching, Colouring
An undirected, unweighted, simple graph $G(V, E)$ is said to be $2$ -colorable if there exists a function $c: V \rightarrow\{0,1\}$ such that for every $(u, v) \in E, c(u) \neq c(v)$ . Which of the following statements about $2$ -colorable graphs is/are true?
MSQ · 2 marks
GATE CS · 2026Graphs: Connectivity, Matching, Colouring
Let $G$ be an undirected graph, which is a path on $8$ vertices. The number of matchings in $G$ is $\_\_\_\_$ . (answer in integer)
NAT · 2 marks
GATE CS · 2026Graphs: Connectivity, Matching, Colouring
Consider a complete graph $K_{n}$ with $n$ vertices ( $n>4$ ). Note that multiple spanning trees can be constructed over $K_{n}$ . Each of these spanning trees is represented as a set of edges. The Jaccard coefficient between any two sets is defined as the ratio of the size of the intersection of the two sets to the size of the union of the two …
MCQ · 2 marks
GATE CS · 2024Graphs: Connectivity, Matching, Colouring
The number of spanning trees in a complete graph of $4$ vertices labelled $\text{A, B, C,}$ and $\text{D}$ is _________.
NAT · 1 mark
GATE CS · 2024Graphs: Connectivity, Matching, Colouring
The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. Let $G$ be any graph with $n$ vertices and chromatic number $k$ . Which of the following statements is/are always TRUE?
MSQ · 2 marks

Browse this topic

More Graphs: Connectivity, Matching, Colouring questions

GATE CS 2002 Q1.25 — Graphs: Connectivity, Matching, Colouring

Related questions