Back to Subject

Unit 4: Graph Theory-I - Practice Quiz

MTH136 — Discrete Structures 60 Questions
0 Correct 0 Wrong 60 Left
0/60

1 In graph theory, a graph is formally defined as an ordered pair consisting of which two sets?

introduction and basic terminology Easy
A. A set of regions and a set of faces
B. A set of paths and a set of cycles
C. A set of nodes and a set of colors
D. A set of vertices and a set of edges

2 Two vertices connected directly by an edge are said to be:

introduction and basic terminology Easy
A. Distant
B. Pendant
C. Isolated
D. Adjacent

3 A graph in which every pair of distinct vertices is connected by an edge is called a:

graphs Easy
A. Complete graph
B. Null graph
C. Bipartite graph
D. Regular graph

4 The complete graph on vertices has how many edges?

graphs Easy
A.
B.
C.
D.

5 A multigraph differs from a simple graph because it allows:

multigraphs Easy
A. No edges at all
B. Multiple edges between the same pair of vertices
C. Only weighted edges
D. Only directed edges

6 An edge that connects a vertex to itself is called a:

multigraphs Easy
A. Bridge
B. Arc
C. Chord
D. Loop

7 The degree of a vertex in a simple graph is defined as:

degree of a vertex Easy
A. The number of edges incident to it
B. The number of paths from it
C. The length of the longest cycle
D. The number of vertices in the graph

8 A vertex with degree is called a(n):

degree of a vertex Easy
A. Isolated vertex
B. Pendant vertex
C. Central vertex
D. Cut vertex

9 A vertex of degree in a graph is known as a:

degree of a vertex Easy
A. Pendant vertex
B. Isolated vertex
C. Bridge vertex
D. Cut vertex

10 According to the Handshaking Theorem, the sum of the degrees of all vertices in a graph equals:

handshaking theorem Easy
A. The number of edges
B. Twice the number of edges
C. Half the number of edges
D. The number of vertices

11 A consequence of the Handshaking Theorem is that the number of vertices of odd degree in any graph is always:

handshaking theorem Easy
A. Prime
B. Odd
C. Zero
D. Even

12 If a graph has edges, what is the sum of the degrees of all its vertices?

handshaking theorem Easy
A.
B.
C.
D.

13 A subgraph of a graph must satisfy which condition?

sub graphs Easy
A. It has more vertices than
B. Its vertices and edges are subsets of those of
C. It contains no edges of
D. It is always a complete graph

14 A subgraph that contains all the vertices of the original graph is called a:

sub graphs Easy
A. Proper subgraph
B. Induced subgraph
C. Complete subgraph
D. Spanning subgraph

15 Two graphs are isomorphic if there exists a one-to-one correspondence between their vertices that preserves:

homeomorphic and isomorphic graphs Easy
A. Adjacency between vertices
B. The vertex labels
C. The color of edges
D. The drawing on paper

16 Which of the following is necessary for two graphs to be isomorphic?

homeomorphic and isomorphic graphs Easy
A. They must be drawn identically
B. They must both be complete
C. They must have the same vertex names
D. They must have the same number of vertices and edges

17 Two graphs are said to be homeomorphic if they can both be obtained from the same graph by:

homeomorphic and isomorphic graphs Easy
A. Reversing edge directions
B. Deleting all edges
C. Adding isolated vertices
D. A series of edge subdivisions

18 A path in a graph is best described as a walk in which:

paths Easy
A. No vertex is repeated
B. Every vertex is repeated
C. Only edges are repeated
D. It always forms a cycle

19 The length of a path in a graph is measured by the number of:

paths Easy
A. Vertices in the path
B. Loops in the path
C. Components in the graph
D. Edges in the path

20 A graph is called connected if:

connectivity Easy
A. It contains a loop
B. Every vertex has the same degree
C. There is a path between every pair of vertices
D. It has no edges

21 A graph has edges. If every vertex has degree , how many vertices does have?

handshaking theorem Medium
A.
B.
C.
D.

22 In a graph, the number of vertices of odd degree is always:

degree of a vertex Medium
A. Zero
B. Equal to number of edges
C. Odd
D. Even

23 The sum of degrees of all vertices in a graph with edges is:

handshaking theorem Medium
A.
B.
C.
D.

24 A complete graph has how many edges?

graphs Medium
A.
B.
C.
D.

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

isomorphic graphs Medium
A. Same drawing on paper
B. Same degree sequence
C. Same number of vertices
D. Same number of edges

26 What distinguishes a multigraph from a simple graph?

multigraphs Medium
A. It has exactly one vertex
B. It cannot be connected
C. It may have multiple edges between the same pair of vertices
D. It must have no edges

27 In a path graph with vertices, what is the diameter?

distance and diameter Medium
A.
B.
C.
D.

28 In a tree with vertices, how many of its edges are bridges?

cut points and bridges Medium
A. No edges
B. All edges
C. Half of the edges
D. Exactly one edge

29 A graph has vertices and connected components, each a tree. How many edges does the graph have?

connected components Medium
A.
B.
C.
D.

30 Can a graph exist with degree sequence ?

handshaking theorem Medium
A. Yes, it is a complete graph
B. Yes, it is a regular graph
C. No, because it has too few vertices
D. No, because the sum of degrees is odd

31 In a simple graph, a walk in which no vertex is repeated is called a:

paths Medium
A. Loop
B. Path
C. Circuit
D. Bridge

32 A spanning subgraph of a graph must satisfy which condition?

subgraphs Medium
A. It contains exactly one vertex
B. It contains all vertices of
C. It is always complete
D. It contains all edges of

33 In a simple graph with vertices, what is the maximum possible degree of any vertex?

degree of a vertex Medium
A.
B.
C.
D.

34 A graph is said to be connected if:

connectivity Medium
A. Every vertex has the same degree
B. It contains a complete subgraph
C. It has no cycles
D. There is a path between every pair of vertices

35 Two graphs are homeomorphic if one can be obtained from the other by:

homeomorphic graphs Medium
A. A series of edge subdivisions
B. Adding new vertices at random
C. Deleting all edges
D. Doubling every edge

36 A -regular graph has edges. How many vertices does it have?

handshaking theorem Medium
A.
B.
C.
D.

37 In a cycle graph (), how many cut vertices exist?

cut points and bridges Medium
A.
B.
C.
D.

38 Two simple graphs each have vertices and edges. Which additional feature must match for them to possibly be isomorphic?

isomorphic graphs Medium
A. Their vertex labels
B. Their coordinate positions
C. Their degree sequences
D. Their drawing orientation

39 In a complete graph with , what is the diameter?

distance and diameter Medium
A.
B.
C.
D.

40 If a simple graph with vertices has exactly connected components, what is the minimum number of edges it can have?

connected components Medium
A.
B.
C.
D.

41 A graph has edges, vertices of degree , and all remaining vertices of degree . How many vertices does have?

handshaking theorem Hard
A.
B.
C.
D.

42 In any finite graph, the number of vertices of odd degree is always:

handshaking theorem Hard
A. Odd
B. Equal to the number of edges
C. A prime number
D. Even

43 Two simple graphs and each have vertices and edges with identical degree sequences . Which statement is correct?

isomorphic graphs Hard
A. They must both be bipartite
B. They cannot be isomorphic
C. They must be isomorphic
D. They may or may not be isomorphic

44 Two graphs are homeomorphic if one can be obtained from the other by:

homeomorphic graphs Hard
A. Adding or removing vertices of degree (edge subdivisions)
B. Contracting all edges to a single vertex
C. Adding a loop at every vertex
D. Deleting any edge

45 A simple graph on vertices has every vertex of degree at least . Which property is guaranteed by Dirac's theorem?

degree of a vertex Hard
A. The graph is a tree
B. The graph is bipartite
C. The graph is Eulerian
D. The graph is Hamiltonian (for )

46 In a connected graph , an edge is a bridge if and only if:

cut points and bridges Hard
A. does not lie on any cycle
B. lies on exactly one cycle
C. connects two vertices of odd degree
D. is incident to a cut vertex

47 For the cycle graph with vertices ( even), what is the diameter?

distance and diameter Hard
A.
B.
C.
D.

48 The vertex connectivity and edge connectivity of a graph with minimum degree satisfy:

connectivity Hard
A. always
B.
C.
D.

49 In a multigraph, which of the following is permitted that is NOT allowed in a simple graph?

multigraphs Hard
A. Paths of length greater than
B. Multiple edges between the same pair of vertices
C. Vertices with degree
D. Vertices of odd degree

50 A spanning subgraph of a graph with vertices and edges must have:

sub graphs Hard
A. At most vertices and exactly edges
B. Fewer than vertices and fewer than edges
C. Exactly vertices and exactly edges
D. Exactly vertices and at most edges

51 A graph with vertices and connected components has at least how many edges?

connected components Hard
A.
B.
C.
D.

52 In a simple connected graph, the length of the longest path (number of edges) between two vertices at distance can be:

paths Hard
A. Exactly
B. Exactly always
C. Greater than or equal to
D. Less than

53 The maximum number of edges in a simple graph on vertices is:

graphs Hard
A.
B.
C.
D.

54 Which of the following is NOT an invariant preserved under graph isomorphism?

isomorphic graphs Hard
A. The labels assigned to vertices
B. The number of connected components
C. The degree sequence
D. The number of edges

55 In a tree with vertices, which statement about cut vertices is true?

cut points and bridges Hard
A. Every leaf is a cut vertex
B. Exactly one vertex is a cut vertex
C. No vertex is a cut vertex
D. Every non-leaf (internal) vertex is a cut vertex

56 In a simple graph with vertices, why must at least two vertices always have the same degree?

degree of a vertex Hard
A. Because the sum of degrees is even
B. Because every graph is regular
C. Because the number of edges is at most
D. Possible degrees range over values but and cannot both occur

57 For the complete bipartite graph with , what is the diameter?

distance and diameter Hard
A.
B.
C.
D.

58 Can a simple graph exist with degree sequence ?

handshaking theorem Hard
A. No, because the degree sum is even but it violates the Erdős–Gallai condition
B. Yes, and it must be regular
C. No, because the degree sum is odd
D. Yes, it is a valid simple graph

59 Removing a single edge from a connected graph can increase the number of components by at most:

connectivity Hard
A. The degree of an endpoint
B.
C.
D.

60 A graph is called -regular if every vertex has degree . For a -regular simple graph on vertices to exist, which condition is necessary?

introduction and basic terminology Hard
A. must be even
B. must equal
C. must be even
D. must be even and
Previous MCQ
Unit 3
Next MCQ
Unit 5