Back to Subject

Unit 4 - Practice Quiz

MTH401 50 Questions
0 Correct 0 Wrong 50 Left
0/50

1 Which of the following describes a simple graph?

A. A graph with multiple edges between the same pair of vertices.
B. A graph containing loops but no multiple edges.
C. A graph with no loops and no multiple edges.
D. A graph where edges have direction.

2 According to the Handshaking Theorem, the sum of degrees of all vertices in an undirected graph is equal to:

A. The number of edges.
B. Twice the number of edges.
C. The number of vertices squared.
D. Half the number of edges.

3 In any undirected graph, the number of vertices with an odd degree is always:

A. Odd
B. Even
C. Prime
D. Zero

4 What is the maximum number of edges in a simple undirected graph with vertices?

A.
B.
C.
D.

5 A vertex with a degree of 0 is called a(n):

A. Pendant vertex
B. Isolated vertex
C. Cut vertex
D. Root vertex

6 A vertex with a degree of 1 is called a(n):

A. Isolated vertex
B. Pendant vertex
C. Internal vertex
D. Universal vertex

7 How many edges does the Complete Graph have?

A. 5
B. 10
C. 20
D. 25

8 Which of the following statements is true for a Complete Bipartite Graph ?

A. The vertex set is partitioned into two sets of size and , and every vertex in one set is connected to every vertex in the other.
B. Every vertex is connected to every other vertex in the graph.
C. It is a graph consisting of a single cycle of length .
D. It is a regular graph of degree .

9 How many edges are there in the Complete Bipartite Graph ?

A. 7
B. 12
C. 24
D. 6

10 A graph in which every vertex has the same degree is called a:

A. Complete graph
B. Bipartite graph
C. -regular graph
D. Connected graph

11 The Cycle Graph (for ) is a regular graph of degree:

A.
B.
C. 2
D. 3

12 How many vertices and edges does the Wheel Graph have?

A. vertices and edges
B. vertices and edges
C. vertices and edges
D. vertices and edges

13 The n-cube (or hypercube) graph has how many vertices?

A.
B.
C.
D.

14 What is the degree of every vertex in the cube graph ?

A. 2
B. 3
C. 4
D. 8

15 A graph is bipartite if and only if:

A. It has no odd cycles.
B. It has no even cycles.
C. It is a complete graph.
D. It is connected.

16 What is the size of the Adjacency Matrix for a graph with vertices?

A.
B.
C.
D.

17 In an adjacency matrix for an undirected simple graph, what does signify?

A. There is a path of length 1 between vertex and vertex .
B. Vertex and vertex are the same.
C. There are multiple edges between and .
D. There is no connection between and .

18 For an undirected graph, the Adjacency Matrix is always:

A. Skew-symmetric
B. Symmetric
C. Identity matrix
D. Lower triangular

19 Let be the adjacency matrix of a simple graph. The entry in the position of (matrix raised to power ) represents:

A. The shortest distance between and .
B. The number of paths of length exactly between and .
C. 1 if there is a path of length , 0 otherwise.
D. The number of edges between and multiplied by .

20 The Incidence Matrix of an undirected graph with vertices and edges has dimensions:

A.
B.
C.
D.

21 In the Incidence Matrix of a simple undirected graph without loops, each column sums to:

A. 0
B. 1
C. 2
D. The degree of the corresponding vertex

22 The sum of the entries in a row of the Adjacency Matrix of an undirected graph represents:

A. The number of edges in the graph.
B. The degree of vertex .
C. The number of loops at vertex .
D. Zero.

23 Two graphs and are isomorphic if:

A. They have the same number of vertices and edges.
B. They have the same degree sequence.
C. There exists a bijection between their vertex sets that preserves adjacency.
D. They can be drawn without crossing edges.

24 Which of the following is NOT an invariant of graph isomorphism? (i.e., property preserved by isomorphism)

A. Number of vertices
B. Number of edges
C. Degree sequence
D. Labels of the vertices

25 A walk in a graph where all edges are distinct is called a:

A. Path
B. Trail
C. Circuit
D. Cycle

26 A path that begins and ends at the same vertex is called a:

A. Cycle (or Circuit)
B. Simple Path
C. Walk
D. Tree

27 An undirected graph is called connected if:

A. It contains a cycle.
B. Every pair of distinct vertices has a path between them.
C. It is a complete graph.
D. Every vertex has an odd degree.

28 A vertex whose removal increases the number of connected components in a graph is called a:

A. Bridge
B. Cut vertex (or Articulation point)
C. Pendant vertex
D. Source

29 An edge whose removal increases the number of connected components is called a:

A. Cut vertex
B. Bridge (or Cut edge)
C. Loop
D. Parallel edge

30 In a directed graph (digraph), the in-degree of a vertex is:

A. The number of edges leaving the vertex.
B. The number of edges entering the vertex.
C. The total number of edges connected to the vertex.
D. The number of loops on the vertex.

31 A directed graph is strongly connected if:

A. There is a path between every pair of vertices in the underlying undirected graph.
B. There is a directed path from to and from to for every pair of vertices .
C. It has no cycles.
D. Every vertex has the same in-degree and out-degree.

32 For a directed graph, the sum of the in-degrees of all vertices is equal to:

A. The sum of the out-degrees.
B. The number of edges.
C. Both A and B.
D. None of the above.

33 Dijkstra’s Algorithm is used to find:

A. The Minimum Spanning Tree.
B. The shortest paths from a single source vertex to all other vertices.
C. The shortest path between every pair of vertices (All-pairs).
D. The topological sort of a graph.

34 Dijkstra’s Algorithm cannot be used on graphs with:

A. Cycles
B. Negative edge weights
C. Directed edges
D. Weighted edges

35 In Dijkstra's algorithm, what represents the initial distance value for the source vertex?

A. Infinity
B. 1
C. 0
D. -1

36 Which data structure is most efficiently used to select the vertex with the minimum distance in Dijkstra's algorithm?

A. Stack
B. Queue
C. Priority Queue (or Min-Heap)
D. Hash Table

37 If the adjacency matrix of a graph is , what type of graph is it?

A.
B.
C. (or Path of length 2)
D.

38 Which of these graphs is NOT bipartite?

A.
B.
C.
D.

39 How many edges are in the cycle graph ?

A. 4
B. 5
C. 10
D. 20

40 In graph theory, two edges are said to be parallel or multiple if:

A. They do not intersect.
B. They are incident on the same pair of vertices.
C. They share exactly one vertex.
D. They have the same weight.

41 Which of the following is true about the complement of a complete graph ?

A. It is also a complete graph.
B. It is a connected graph.
C. It is a null graph (graph with no edges).
D. It is a cycle graph.

42 If a graph has vertices and edges and is connected, what is the minimum value for ?

A.
B.
C.
D.

43 The degree sequence of a graph is 4, 4, 4, 2, 2. What is the sum of the degrees?

A. 12
B. 16
C. 10
D. 20

44 Based on the degree sequence 4, 4, 4, 2, 2, how many edges does the graph have?

A. 16
B. 8
C. 32
D. 4

45 What is a Sub-graph?

A. A graph with half the vertices of the original.
B. A graph where and .
C. The complement of a graph.
D. A graph that is isomorphic to the original.

46 Which of the following graphs is Regular?

A.
B.
C.
D. Path graph

47 Consider a directed graph. If there is a path from vertex to vertex , is reachable from ?

A. Yes
B. No
C. Only if the graph is undirected
D. Only if the path is length 1

48 If a simple connected planar graph has vertices, edges, and faces, Euler's formula states:

A.
B.
C.
D.

49 What is the Out-degree of vertex A in the graph with edges: , , ?

A. 1
B. 2
C. 3
D. 0

50 Which graph represents the 1-skeleton of a tetrahedron?

A.
B.
C.
D.
Previous MCQ
Unit 3
Next MCQ
Unit 5