1.What is a graph?
a) A collection of vertices and edges
b) A sequence of numbers
c) A set of equations
d) A type of geometric shape
Answer: a) A collection of vertices and edges
Explanation: In graph theory, a graph consists of a set of vertices (nodes) and a set of edges (connections) that link pairs of vertices.
2.What is the degree of a vertex in a graph?
a) The number of vertices in the graph
b) The number of edges incident to the vertex
c) The length of the shortest path to another vertex
d) The sum of the weights of adjacent edges
Answer: b) The number of edges incident to the vertex
Explanation: The degree of a vertex in a graph is the number of edges incident to that vertex.
3.How many edges does a complete graph with n vertices have?
a) n
b) n(n-1)
c) n(n+1)/2
d) (n-1)(n-2)/2
Answer: c) n(n+1)/2
Explanation: In a complete graph with n vertices, each vertex is connected to every other vertex, resulting in n(n-1)/2 edges.
4.What is an Eulerian path in a graph?
a) A path that visits every vertex exactly once
b) A path that visits every edge exactly once
c) A path that starts and ends at the same vertex
d) A path that traverses every edge exactly twice
Answer: b) A path that visits every edge exactly once
Explanation: An Eulerian path in a graph is a path that traverses every edge exactly once.
5.What does the chromatic number of a graph represent?
a) The number of edges in the graph
b) The maximum degree of a vertex in the graph
c) The minimum number of colors needed to color the vertices so that no adjacent vertices have the same color
d) The number of connected components in the graph
Answer: c) The minimum number of colors needed to color the vertices so that no adjacent vertices have the same color
Explanation: The chromatic number of a graph is the minimum number of colors required to color the vertices of the graph so that no two adjacent vertices share the same color.
6.What is the complement of a graph?
a) A graph obtained by reversing the direction of each edge
b) A graph obtained by removing some edges
c) A graph obtained by swapping the positions of vertices
d) A graph obtained by connecting vertices that were not connected in the original graph and vice versa
Answer: d) A graph obtained by connecting vertices that were not connected in the original graph and vice versa
Explanation: The complement of a graph contains all the edges not present in the original graph, and vice versa.
7.What is a Hamiltonian cycle in a graph?
a) A cycle that visits every vertex exactly once
b) A cycle that visits every edge exactly once
c) A cycle that starts and ends at the same vertex
d) A cycle that traverses every edge exactly twice
Answer: a) A cycle that visits every vertex exactly once
Explanation: A Hamiltonian cycle in a graph is a cycle that visits every vertex exactly once.
8.What is the number of edges in a tree with n vertices?
a) n
b) n-1
c) n(n-1)/2
d) n^2
Answer: b) n-1
Explanation: A tree with n vertices has exactly n-1 edges, as there is exactly one unique path between any two vertices in a tree.
9.What is the chromatic number of a bipartite graph?
a) 1
b) 2
c) 3
d) It varies depending on the number of vertices
Answer: b) 2
Explanation: Bipartite graphs have a chromatic number of 2, as they can be colored using only two colors such that no two adjacent vertices have the same color.
10.What is a planar graph?
a) A graph with a planar representation
b) A graph with a Hamiltonian cycle
c) A graph with a chromatic number of 3
d) A graph with no edges
Answer: a) A graph with a planar representation
Explanation: A planar graph is a graph that can be drawn in a plane without any edges crossing.
11.What is the handshake lemma in graph theory?
a) Every vertex in a graph has an even degree
b) The sum of the degrees of all vertices in a graph is twice the number of edges
c) Every edge in a graph connects two distinct vertices
d) A graph with no cycles is called a tree
Answer: b) The sum of the degrees of all vertices in a graph is twice the number of edges
Explanation: The handshake lemma states that the sum of the degrees of all vertices in a graph is twice the number of edges, as each edge contributes to the degree of two vertices.
12.What is a multigraph?
a) A graph with multiple components
b) A graph with multiple edges between the same pair of vertices
c) A graph with directed edges
d) A graph with self-loops
Answer: b) A graph with multiple edges between the same pair of vertices
Explanation: A multigraph is a graph that allows multiple edges between the same pair of vertices.
13.What is a simple graph?
a) A graph with no edges
b) A graph with no cycles
c) A graph with no self-loops or multiple edges between the same pair of vertices
d) A graph with no isolated vertices
Answer: c) A graph with no self-loops or multiple edges between the same pair of vertices
Explanation: A simple graph is a graph that has no self-loops and no multiple edges between the same pair of vertices.
14.What is the chromatic polynomial of a graph?
a) A polynomial that determines the chromatic number of the graph
b) A polynomial that counts the number of cycles in the graph
c) A polynomial that represents the degree sequence of the graph
d) A polynomial that counts the number of spanning trees in the graph
Answer: a) A polynomial that determines the chromatic number of the graph
Explanation: The chromatic polynomial of a graph is a polynomial that counts the number of proper vertex colorings of the graph, and its smallest real root gives the chromatic number of the graph.
15.What is a cut vertex in a graph?
a) A vertex that is adjacent to all other vertices in the graph
b) A vertex whose removal increases the number of connected components in the graph
c) A vertex that does not belong to any cycle in the graph
d) A vertex with the highest degree in the graph
Answer: b) A vertex whose removal increases the number of connected components in the graph
Explanation: A cut vertex, or articulation point, is a vertex in a graph whose removal increases the number of connected components in the graph.
16.What is a planar embedding of a graph?
a) A drawing of the graph in the plane with no edges crossing
b) A representation of the graph as a matrix
c) A decomposition of the graph into its connected components
d) A labeling of the vertices and edges of the graph
Answer: a) A drawing of the graph in the plane with no edges crossing
Explanation: A planar embedding of a graph is a drawing of the graph in the plane such that no edges intersect.
17.What is the chromatic index of a graph?
a) The maximum degree of a vertex in the graph
b) The number of colors used to color the vertices of the graph
c) The minimum number of colors needed to color the edges of the graph so that no adjacent edges have the same color
d) The number of edges incident to a vertex
Answer: c) The minimum number of colors needed to color the edges of the graph so that no adjacent edges have the same color
Explanation: The chromatic index of a graph is the minimum number of colors needed to color the edges of the graph so that no two adjacent edges have the same color.
18.What is a matching in a graph?
a) A set of edges with no common vertices
b) A set of vertices with no common edges
c) A set of edges with a common vertex
d) A set of vertices with a common edge
Answer: a) A set of edges with no common vertices
Explanation: A matching in a graph is a set of edges in which no two edges share a common vertex.
19.What is a cycle in a graph?
a) A set of vertices with no common edges
b) A set of edges with no common vertices
c) A connected subgraph with no cycles
d) A connected subgraph with at least one cycle
Answer: d) A connected subgraph with at least one cycle
Explanation: A cycle in a graph is a connected subgraph in which there is a path from each vertex to every other vertex, and the first and last vertices of the path are the same.
20.What is the purpose of the chromatic polynomial of a graph?
a) To determine the maximum degree of a vertex in the graph
b) To count the number of cycles in the graph
c) To calculate the number of spanning trees in the graph
d) To determine the chromatic number of the graph
Answer: d) To determine the chromatic number of the graph
Explanation: The chromatic polynomial of a graph is used to determine the chromatic number of the graph, which represents the minimum number of colors needed to color the vertices of the graph such that no two adjacent vertices have the same color.