Graph Theory MCQs

Correct Answer: a) The number of edges connected to it

Explanation:
The degree of a vertex in an undirected graph is the number of edges incident to it. Each loop contributes 2 to the degree of the vertex.
Short Trick: Count the number of connections from a vertex.

Correct Answer: c) n(n-1)/2

Explanation:
In a simple graph with n vertices, each vertex can connect to at most (n-1) other vertices. Counting all possible connections gives n(n-1)/2 edges.
Short Trick: Use the formula \(\binom{n}{2} = \frac{n(n-1)}{2}\) for combinations of 2 elements from n elements.

Correct Answer: a) A sequence of vertices where each adjacent pair is connected by an edge

Explanation:
A walk is a sequence of vertices and edges, starting and ending at vertices, where each vertex is incident to the edges that come before and after it in the sequence. In a walk, both vertices and edges can be repeated.
Short Trick: Think of it as tracing a path with your finger, where you can revisit vertices and edges.

Correct Answer: b) A path where no vertex is repeated

Explanation:
A simple path (or just "path") is a walk in which no vertex appears more than once. Since each vertex appears at most once, each edge also appears at most once.
Short Trick: A path without vertex repetition is a simple path.

Correct Answer: c) A graph where there is a path between every pair of vertices

Explanation:
A graph is connected if there is a path between every pair of vertices. In other words, the graph consists of a single connected component.
Short Trick: You can reach any vertex from any other vertex by following edges.

Correct Answer: b) A graph where every vertex is connected to every other vertex

Explanation:
A complete graph K_n is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. Therefore, every vertex is connected to every other vertex.
Short Trick: In K_n, every vertex has degree (n-1), and there are n(n-1)/2 edges in total.

Correct Answer: c) A graph containing exactly one cycle with n vertices

Explanation:
A cycle graph C_n is a connected graph with n vertices where each vertex has exactly two adjacent vertices. It forms a single cycle of length n.
Short Trick: Think of it as vertices arranged in a circle, with each vertex connected to its two neighbors.

Correct Answer: b) A graph where all vertices have the same degree

Explanation:
A regular graph is a graph where each vertex has the same degree. If each vertex has degree k, then the graph is called a k-regular graph.
Short Trick: In a regular graph, all vertices have an equal number of connections.

Correct Answer: a) A cycle graph with an additional central vertex connected to all cycle vertices

Explanation:
A wheel graph W_n consists of a cycle graph C_n-1 with an additional central vertex that is connected to all vertices of the cycle.
Short Trick: Think of it as a wheel with spokes, where the hub is connected to all points on the rim.

Correct Answer: c) A graph whose vertices can be divided into two disjoint sets such that no two vertices within the same set are adjacent

Explanation:
A bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to a vertex in V. No edge connects vertices within the same set.
Short Trick: You can color all vertices using only two colors such that no adjacent vertices have the same color.

Correct Answer: b) A bipartite graph with m vertices in one set and n vertices in the other set, with all possible edges between the sets

Explanation:
K_m,n is a complete bipartite graph with m vertices in one partition and n vertices in the other partition, where every vertex in the first partition is connected to every vertex in the second partition.
Short Trick: In K_m,n, there are m×n edges connecting the two partitions.

Correct Answer: c) A graph representing the edges and vertices of a cube

Explanation:
A cube graph Q₃ is the graph of vertices and edges of the 3-dimensional hypercube. It has 2³ = 8 vertices and 3×2² = 12 edges.
Short Trick: The vertices of Q₃ correspond to the 8 corners of a cube, and the edges correspond to the 12 edges of the cube.

Correct Answer: b) 1 if there is an edge between vertices i and j, 0 otherwise

Explanation:
In an adjacency matrix representation of a simple undirected graph, A[i][j] = 1 if there is an edge between vertices i and j, and A[i][j] = 0 otherwise. For weighted graphs, A[i][j] would be the weight of the edge.
Short Trick: The adjacency matrix shows connections (1) or lack thereof (0) between vertices.

Correct Answer: b) It is symmetric

Explanation:
In an undirected graph, if there is an edge between vertices i and j, then there is also an edge between vertices j and i. This makes the adjacency matrix symmetric, meaning A[i][j] = A[j][i] for all i and j.
Short Trick: An undirected graph's adjacency matrix is symmetric about the main diagonal.

Correct Answer: b) A matrix where rows represent vertices and columns represent edges

Explanation:
The incidence matrix of a graph is a matrix that shows the relationship between vertices and edges. In this matrix, rows correspond to vertices and columns correspond to edges. For an undirected graph, the entry is 1 if the vertex is incident to the edge, and 0 otherwise.
Short Trick: The incidence matrix shows which vertices are connected by which edges.

Correct Answer: b) The list of all vertices it is connected to

Explanation:
In the adjacency list representation, each vertex has a list of all the vertices it is connected to by an edge. For weighted graphs, the weight of each edge might also be stored.
Short Trick: Think of it as a phonebook where each person (vertex) has a list of their friends (connected vertices).

Correct Answer: c) There is a one-to-one correspondence between their vertices that preserves adjacency

Explanation:
Two graphs G and H are isomorphic if there is a bijection (one-to-one correspondence) between their vertex sets that preserves adjacency. In other words, vertices v and w are adjacent in G if and only if their corresponding vertices f(v) and f(w) are adjacent in H.
Short Trick: Isomorphic graphs have the same structure but possibly different vertex labels.

Correct Answer: d) All of the above

Explanation:
For two graphs to be isomorphic, they must have the same number of vertices, the same number of edges, and the same degree sequence. However, these conditions alone are not sufficient to guarantee isomorphism. There are non-isomorphic graphs that share all these properties.
Short Trick: These are structural similarities that isomorphic graphs must share, but having them doesn't guarantee isomorphism.

Correct Answer: a) They are definitely not isomorphic

Explanation:
If two graphs have different degree sequences, they cannot be isomorphic. This is because isomorphism preserves vertex degrees: if a vertex has degree d in one graph, its corresponding vertex in an isomorphic graph must also have degree d.
Short Trick: Different degree sequences ensure different graph structures.