Question

Let \(G=(V, E)\) and \(H=\left(V_{1}, E_{1}\right)\) be isomorphic graphs. Prove the degrees of the vertices of \(G\) are exactly the degrees of the vertices of \(H .\) Show that \(|V|=\left|V_{1}\right|\) and \(|E|=\left|E_{1}\right|\) alone do not imply that \(G\) and \(H\) are isomorphic.

Short answer

Vertex degrees are preserved by isomorphism; vertex and edge count alone cannot confirm isomorphism without structural integrity.

Step-by-step solution

Define Isomorphic Graphs

Graphs \(G\) and \(H\) are isomorphic if there is a bijection \(f\): \(V \rightarrow V_1\) such that for every edge \((u, v)\) in \(G\), \((f(u), f(v))\) is an edge in \(H\). This bijection preserves the edges and the degree of each vertex.

Show Vertex Degrees are Preserved

Consider a vertex \(v\) in \(G\) with degree \(d_G(v)\). Since \(f\) is bijective and maps a vertex in \(G\) to a vertex in \(H\), the degree of the corresponding vertex \(f(v)\) in \(H\) must also be \(d_H(f(v)) = d_G(v)\). Thus, the function preserves vertex degrees.

Verify Equal Vertex and Edge Counts Are Insufficient for Isomorphism

Graphs having the same number of vertices \(|V| = |V_1|\) and edges \(|E| = |E_1|\) does not ensure they are isomorphic. For example, consider two graphs each with 4 vertices and two edges: one graph having parallel edges and the other having a single edge between different pairs of vertices; these are not isomorphic due to different adjacency structures.

Key concepts

Vertex Degree Preservation

When we talk about vertex degree preservation in isomorphic graphs, we are referring to the property that isomorphic graphs must maintain the same degree for their corresponding vertices. The degree of a vertex is the number of edges connected to it. If two graphs are isomorphic, then their structure is essentially a rearrangement of nodes (vertices) connected by edges, without altering the connection pattern.
For example, consider vertices in graph G and graph H. If vertex A in graph G has 3 connections, when mapping it to vertex B in graph H, vertex B must also have 3 connections.
The bijection—the one-to-one correspondence—between the vertices of G and H ensures this preservation. This concept is crucial for proving that two graphs are indeed isomorphic.

Bijection in Graph Theory

A bijection is a special kind of function that creates a perfect 'pairing' between elements of two sets. In the context of graph theory, a bijection comes into play when defining isomorphic graphs. It allows us to map each vertex in one graph to a unique vertex in another graph, effectively preserving connections and properties, such as vertex degrees.
In simpler terms, a bijection ensures that every element (vertex) in the first graph (G) is paired with exactly one element in the second graph (H), and vice versa. This perfect matching ensures that the structure and connectivity of the graphs are maintained.

• Injective: Every vertex in G maps to a unique vertex in H.
• Surjective: Every vertex in H has a vertex in G mapping to it.

This combined injective and surjective property guarantees there's no missing or overlapping pair, maintaining the integrity of both graphs' structures.

Vertex and Edge Count in Graphs

When comparing two graphs to determine isomorphism, it might seem that having the same number of vertices and edges should be sufficient. However, this is not the case. Isomorphism requires a more in-depth look into how these vertices and edges are connected.
Two graphs could have the same number of vertices and edges yet differ significantly in their arrangement. Consider two hypothetical graphs, each with 4 vertices and 3 edges. Graph I might have all its edges connected to a single vertex creating a star-like structure, while Graph II could form a simple triangle with an extra vertex,
meaning they share the vertex and edge counts but differ in structure. Therefore, examining the vertex and edge count alone is not enough for determining if two graphs are isomorphic.

Adjacency Structures in Graphs

The adjacency structure of a graph details how its vertices are connected by edges. Understanding adjacency structures is fundamental when assessing graph isomorphism, as it involves more than just comparing vertex and edge counts.
For two graphs to be isomorphic, their adjacency matrices must be rearrangeable into each other by permuting rows and columns. This means that corresponding vertices must share the same neighbors.
Let's say in one graph, vertex X is connected to vertex Y and Z, and in the second graph, if vertex A is mapped to X, then A must also be connected to the vertices mapped to Y and Z.

• Preserves connectivity: Maps every connection from graph G to graph H.
• Maintains integrity: Ensures that even the complex inner connections remain unchanged.

The structure formed by these connections is crucial for determining whether two graphs are just different representations of the same entity, i.e., are isomorphic.