Graph Representations and Basics MCQs: 12 Solved Questions with Explanations

Graph-representation questions turn small wording changes into different storage, degree, and counting rules. Attempt each question before checking the explanation, and use the linked question title when you need the longer worked solution.

Related reading: graph theory MCQs and graph data structure MCQs.

Graph basics MCQs: definitions, regular graphs, and storage terms

Q1. What is a graph in the context of computer science? (CoCubes 2025)

• (a) A data structure that consists of nodes connected by edges

• (b) A pictorial representation of statistical data

• (c) A mathematical function

• (d) None of the above

Correct answer: (a). A graph stores vertices and the edges that relate pairs of vertices. Here, graph means the computer-science data structure, not the statistical chart described by option (b).

Q2. A graph in which all nodes are of equal degree, is known as (ISRO 2009)

• (a) Multigraph

• (b) Non regular graph

• (c) Regular graph

• (d) Complete graph

Correct answer: (c). A regular graph is one in which every vertex has the same degree. Every complete graph is regular, but a regular graph need not be complete, as shown by a 4-cycle in which every vertex has degree 2.

Q3. Let X be the adjacency matrix of a graph G with no self loops. The entries along the principal diagonal of X are (ISRO 2007; BEL 2007)

• (a) all zeros

• (b) all ones

• (c) both zeros and ones

• (d) different

Correct answer: (a). The diagonal entry X[i][i] records whether vertex i has an edge to itself. With no self-loops, every such entry is 0, whether the graph is directed or undirected.

Q4. Maintaining a graph in memory by means of its adjacency matrix is known as: (UGC NET 2025)

• (a) Complete Representation

• (b) Linked Representation

• (c) Circular Representation

• (d) Sequential Representation

Correct answer: (d). An adjacency matrix is a two-dimensional sequential array, while adjacency lists give the linked representation. The term describes how the graph is stored, not whether the graph itself is complete.

Adjacency matrix and adjacency list MCQs: space, pointers, and cycles

Q5. In an adjacency list representation of an undirected simple graph $G = (V,E)$, each edge $(u, v)$ has two adjacency list entries: [$v$] in the adjacency list of $u$, and [$u$] in the adjacency list of $v$. These are called twins of each other. A twin pointer is a pointer from an adjacency list entry to its twin. If |$E$| = $m$ and |$V$| = $n$, and the memory size is not a constraint, what is the time complexity of the most efficient algorithm to set the twin pointer in each entry in each adjacency list? (GATE 2016)

• (a) $\Theta(n^2)$

• (b) $\Theta(n+m)$

• (c) $\Theta(m^2)$

• (d) $\Theta(n^4)$

Correct answer: (b). Initialise per-vertex bookkeeping in $\Theta(n)$, then scan the $2m$ adjacency entries once and pair each $(u,v)$ entry with $(v,u)$ through direct auxiliary lookup or hashing. The total is $\Theta(n+m)$, and simply visiting the whole representation already takes that order of time.

Q6. Consider a simple undirected unweighted graph with at least three vertices. If A is the adjacency matrix of the graph, then the number of 3-cycles in the graph is given by the trace of (GATE 2022)

• (a) A³

• (b) A³ divided by 2

• (c) A³ divided by 3

• (d) A³ divided by 6

Correct answer: (d). The diagonal entries of A³ count closed walks of length 3. Each undirected triangle is counted from 3 possible starting vertices and in 2 directions, so trace(A³) counts it $3 \times 2 = 6$ times and the number of 3-cycles is trace(A³)/6.

For a wider sequence of GATE-level DSA topics after these matrix questions, continue with GATE Guidance by Sanchit Sir.

Graph edge and degree MCQs: complete graphs and the handshaking lemma

Q7. If complete graph have ‘n’ nodes, then it will have how many edges? (DSSSB 2021)

• (a) n(n-1)/2

• (b) (n-1)/2

• (c) n/2

• (d) n(n-1)/4

Correct answer: (a). Each edge selects an unordered pair of distinct vertices, so the count is $C(n,2) = n(n-1)/2$. For $n=6$, this gives $6 \times 5/2 = 15$ edges.

Q8. The number of vertices in an undirected graph with odd degree is always _____. (DSSSB 2021)

• (a) Odd number

• (b) Even number

• (c) Zero

• (d) Prime number

Correct answer: (b). By the handshaking lemma, the sum of all degrees is $2|E|$, which is even. An even sum can contain only an even number of odd addends, so the number of odd-degree vertices must be even, although it may be zero.

Q9. Sum of degrees of all nodes for a graph G(V, E) can be given by: (HTET 2022)

• (a) |E|

• (b) 2 × |E|

• (c) 2 × |V|

• (d) |V|

Correct answer: (b). Every undirected edge contributes 1 to the degree of each endpoint, hence 2 to the total. If $|E|=7$, the sum of all vertex degrees is $2 \times 7 = 14$, even when those edges are distributed unevenly.

The earlier Graph MCQs: 10 Solved BFS, DFS, Connectivity (GATE) surveys representations, traversals, and connectivity. Its twin-pointer and triangle-trace questions also appear here as representation anchors; this set extends that foundation into regular graphs, degree identities, self-loops, and labelled-graph counting.

Directed graph degrees and undirected self-loop MCQs

Q10. In directed graph G(V, E) where V = {P, Q, R, S, T} and E = {PQ, RS, TP, PS, QR, PT, ST, QP, RQ, TS}, the vertex with maximum in-degree is ......... and vertex with maximum out-degree is ......... . (HTET 2022)

• (a) P, S

• (b) T, Q

• (c) Q, R

• (d) S, P

Correct answer: (d). Reading every edge once by destination gives in-degrees P=2, Q=2, R=1, S=3, T=2; reading them once by source gives out-degrees P=3, Q=2, R=2, S=1, T=2. Both columns sum to the 10 listed edges, so S has maximum in-degree and P has maximum out-degree.

Q11. Pick up the wrong statement for calculating degree of a node in a graph: (CDAC CCAT 2017)

• (a) For every regular edge on a vertex is counted as 1

• (b) For a self-loop it is counted as 2

• (c) Sum of all the edges on a vertex

• (d) Sum of all the edges in the graph

Correct answer: (d). A vertex degree depends on the edges incident on that vertex, not the total edge count of the graph. One self-loop contributes 2 because it meets the same vertex at both ends, so one loop plus two ordinary incident edges gives degree $2+1+1=4$.

Counting labelled undirected graphs from the possible edge set

Q12. How many undirected graphs (not necessarily connected) can be constructed out of a given set V = {V₁, V₂, ..., Vₙ} of n vertices? (TPSC 2025)

• (a) n(n − 1)/2

• (b) 2ⁿ

• (c) n!

• (d) 2^(n(n − 1)/2)

Correct answer: (d). There are $C(n,2)=n(n-1)/2$ possible undirected edges on $n$ labelled vertices, and each can independently be present or absent. For $n=4$, there are $4 \times 3/2=6$ possible pairs and therefore $2^6=64$ graphs, including the empty graph and the complete graph.

Graph representations and basics: the five traps behind the answers

These questions become easier when you identify the cue before touching the options.

An adjacency matrix uses $\Theta(V^2)$ space and provides constant-time edge lookup. An adjacency list uses $\Theta(V+E)$ space, but finding a particular neighbour requires scanning that vertex's list. Q5 asks for pairing all adjacency entries, so its $\Theta(n+m)$ result is fully consistent with these standard representation costs.

Where these 12 graph MCQs fit in your preparation

Q1-Q4 test vocabulary and representations, Q5-Q6 test matrix and list reasoning, Q7-Q9 cover undirected counting and degree identities, Q10-Q11 cover directed degrees and loops, and Q12 tests labelled-graph counting. Try the set again after one week, writing the relevant formula or invariant before choosing an option.

For the next conceptual step, study Graph Algorithms: BFS, DFS and Shortest Paths. Choose DSA using Java when you want a structured, implementation-oriented route, or browse Coding & DSA to compare broader programming and DSA paths.