Question

Two graphs $G_1$ and $G_2$ are isomorphic if which of the following conditions is satisfied?

• A. Both graphs have the same number of vertices only
• B. Both graphs have the same number of edges only
• C. There exists a one-to-one correspondence between their vertices that preserves adjacency
• D. Both graphs have the same number of vertices but different edges

Hint:

Think of isomorphism as "renaming" vertices. If you can rename the vertices of graph A to match the labels of graph B such that the edge list becomes identical, the graphs are isomorphic.

Answer 1

The Correct Option is C

Concept: Graph isomorphism is a concept in discrete mathematics where two graphs are considered "the same" structurally, even if they are drawn differently.
• Bijection: There must be a one-to-one and onto mapping (isomorphism) between the vertex sets of the two graphs.
• Adjacency Preservation: If two vertices are connected by an edge in the first graph, their corresponding mapped vertices must be connected by an edge in the second graph.

Step 1: Analyzing the necessity vs. sufficiency of conditions.
Options (A) and (B) describe "invariants." While it is true that isomorphic graphs must have the same number of vertices and edges, these conditions alone are not enough to prove isomorphism. Many graphs share these counts but have entirely different connection structures.

Step 2: Identifying the formal definition.
The formal mathematical definition of isomorphism states that $G_1 \simeq G_2$ if there exists a bijection $f: V(G_1) \rightarrow V(G_2)$ such that for any two vertices $u, v \in V(G_1)$, they are adjacent in $G_1$ if and only if $f(u)$ and $f(v)$ are adjacent in $G_2$. This is precisely what is described in option (C).

Step 3: Refuting the incorrect scenario.
Option (D) suggests having the same number of vertices but different edges; this would explicitly make the graphs non-isomorphic because their edge counts (an invariant) must match perfectly.