Back to Subject
View Notes

Unit 4 - Practice Quiz

MTH401

1 A graph consists of a set of vertices and a set of edges . If the edges have a direction associated with them, the graph is called a:

A. Simple Graph
B. Undirected Graph
C. Directed Graph (Digraph)
D. Connected Graph

2 According to the Handshaking Lemma, 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. Half the number of edges
D. The number of vertices

3 In a simple undirected graph, the maximum number of edges with vertices is:

A.
B.
C.
D.

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

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

5 A vertex with a degree of 1 is called a:

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

6 Which of the following statements is true regarding the number of vertices with odd degrees in an undirected graph?

A. There must be an odd number of such vertices.
B. There must be an even number of such vertices.
C. There can be any number of such vertices.
D. There are no vertices with odd degrees.

7 A Complete Graph is a simple graph where:

A. There is exactly one path between any pair of vertices.
B. Every pair of distinct vertices is connected by a unique edge.
C. The graph forms a closed loop.
D. The set of vertices can be partitioned into two disjoint sets.

8 How many edges does the cycle graph (where ) have?

A.
B.
C.
D.

9 A Regular Graph is a graph where:

A. Every vertex has the same degree.
B. Every edge has the same weight.
C. The graph is connected.
D. There are no cycles.

10 A Wheel Graph is obtained by taking a cycle graph and adding:

A. One edge connecting two existing vertices.
B. One additional vertex connected to all existing vertices.
C. Another cycle graph.
D. Two additional vertices connected to each other.

11 How many vertices and edges does the Wheel Graph have? (Note: definition assumes is the size of the outer cycle)

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

12 The -dimensional Hypercube (or -cube), denoted , has how many vertices?

A.
B.
C.
D.

13 What is the degree of every vertex in the -cube ?

A. 2
B.
C.
D.

14 A graph is Bipartite if and only if:

A. It contains no cycles.
B. It is a complete graph.
C. Its vertex set can be partitioned into two disjoint sets such that every edge connects a vertex in one set to one in the other.
D. Every vertex has an even degree.

15 Which of the following Cycle graphs is Bipartite?

A.
B.
C.
D.

16 A Complete Bipartite Graph has how many edges?

A.
B.
C.
D.

17 If a graph has vertices, what is the dimension of its Adjacency Matrix?

A.
B.
C.
D.

18 For a simple undirected graph, the adjacency matrix is always:

A. Asymmetric
B. Symmetric
C. Identity
D. Zero matrix

19 In the adjacency matrix of a graph, the sum of the entries in row represents:

A. The number of vertices in the graph.
B. The degree of vertex (for undirected graphs).
C. The number of paths of length 2.
D. The weight of the edges.

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

A. The distance between and .
B. The number of paths of length exactly from to .
C. The number of edges between and .
D. Whether and are connected.

21 An Incidence Matrix for an undirected graph with vertices and edges has dimensions:

A.
B.
C.
D.

22 In an incidence matrix for a simple undirected graph, the sum of entries in any column is:

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

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 preserving adjacency.
D. Their adjacency matrices are identical.

24 Which of the following is an invariant property preserved under graph isomorphism?

A. The labels of the vertices.
B. The exact visual drawing of the graph.
C. The degree sequence of the graph.
D. The order of vertices in the adjacency matrix.

25 A Walk in a graph where no edges are repeated is called a:

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

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

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

27 An undirected graph is called Connected if:

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

28 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. Every vertex has an out-degree of at least 1.
D. It contains no directed cycles.

29 A directed graph is Weakly Connected if:

A. The underlying undirected graph is connected.
B. It is strongly connected.
C. Every node has in-degree 1.
D. It is a set of disjoint components.

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

A. Pendant vertex
B. Cut vertex (Articulation Point)
C. Isolated vertex
D. Source vertex

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

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

32 Dijkstra’s Algorithm is used to find:

A. The Minimum Spanning Tree.
B. The shortest path from a single source to all other vertices.
C. The shortest path between all pairs of vertices.
D. The topological sort of a graph.

33 Dijkstra’s algorithm requires that the edge weights are:

A. Integers
B. Positive
C. Non-negative
D. Negative

34 What data structure is most efficiently used to select the next vertex with the minimum distance in Dijkstra’s algorithm?

A. Stack
B. Queue
C. Priority Queue (or Min-Heap)
D. Linked List

35 In Dijkstra's algorithm, the operation of updating the distance of a neighbor of the current vertex is called:

A. Relaxation
B. Contraction
C. Expansion
D. Rotation

36 What is the time complexity of Dijkstra’s algorithm using a binary heap for a graph with vertices and edges?

A.
B.
C.
D.

37 Which algorithm strategy does Dijkstra's algorithm follow?

A. Dynamic Programming
B. Divide and Conquer
C. Greedy Approach
D. Backtracking

38 The complement of a simple graph has the same vertex set as , and two vertices are connected in if and only if:

A. They are connected in .
B. They are NOT connected in .
C. One is a neighbor of the other in .
D. They have the same degree in .

39 What is the size of the Edge set for ?

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

40 A simple graph is Planar if:

A. It can be drawn in the plane without edges crossing.
B. It is connected.
C. It is bipartite.
D. It has fewer than 5 vertices.

41 Which graph is known as the Peterson Graph?

A.
B.
C. A specific graph with 10 vertices and 15 edges
D.

42 The in-degree of a vertex in a directed graph 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. Always equal to the out-degree.

43 For any directed graph, the sum of in-degrees is equal to:

A. The sum of out-degrees.
B. Twice the number of edges.
C. The number of vertices.
D. Zero.

44 What is the maximum number of edges in a simple bipartite graph with sets of size and ?

A.
B.
C.
D.

45 A graph with no loops and no parallel edges is called a:

A. Multigraph
B. Pseudograph
C. Simple Graph
D. Weighted Graph

46 The length of a path in a graph is defined as:

A. The number of vertices in the path.
B. The number of edges in the path.
C. The sum of degrees of vertices in the path.
D. The number of vertices minus one.

47 Two distinct vertices and are adjacent if:

A. There is a path between them.
B. There is an edge connecting them directly.
C. They have the same degree.
D. They belong to the same component.

48 If the adjacency matrix of a graph contains 1s on the main diagonal, it indicates the graph has:

A. Cycles
B. Self-loops
C. Parallel edges
D. Disconnected components

49 Which of the following is NOT a necessary condition for two graphs to be isomorphic?

A. Same number of vertices
B. Same number of edges
C. Same number of circuits of a particular length
D. Same adjacency matrix representation without reordering

50 In a directed graph, a path is simple if:

A. All edges are distinct.
B. All vertices are distinct.
C. Only the start and end vertices are the same.
D. The direction of edges is ignored.