Isomorphic (Equivalent) Connected Graphs and Adjacency Matrices Revision Notes for VCE SSCE General Mathematics

Isomorphic (Equivalent) Connected Graphs and Adjacency Matrices

Introduction

Graph theory provides powerful tools for representing and analysing networks and relationships. This note covers three important concepts: connected graphs, isomorphic graphs, and adjacency matrices. These ideas are fundamental to understanding how information flows through networks and how different graph representations can contain identical information.

infoNote

These three concepts form the foundation for analysing network structures in computer science, engineering, and many other fields. Understanding how graphs connect, when they're equivalent, and how to represent them mathematically is essential for solving real-world problems.

Connected graphs and bridges

What is a connected graph?

A connected graph is one where every vertex can be reached from every other vertex. This means you can always find a path along the edges from any starting vertex to any destination vertex, either directly or by travelling through intermediate vertices.

All three graphs shown above are connected because starting from any vertex (say vertex $A$ ), you can travel along edges to reach every other vertex in the graph.

Disconnected graphs

In contrast, a graph is disconnected if there is at least one pair of vertices with no path connecting them.

These three graphs are not connected. For example, in each graph, vertex $A$ cannot reach all other vertices through the available edges.

What is a bridge?

In network planning and design, certain connections are critical to maintaining connectivity. These critical edges are called bridges.

Bridge: A bridge is an edge in a connected graph that, if removed, would leave the graph disconnected.

chatImportant

Understanding bridges is crucial in applications such as:

Planning airline routes
Designing communication systems
Building computer networks

In these systems, a single missing connection (bridge) can cause the entire network to fail. Identifying bridges helps network designers understand vulnerable points that need backup connections or extra protection.

In Graph 1, edge $CD$ is a bridge. When we remove edge $CD$ , the graph becomes disconnected as shown in Graph 2. Vertex $D$ is now isolated from the other vertices.

infoNote

Real-world bridges in infrastructure are named after this graph theory concept, as they provide critical connections between separated areas. The mathematical concept captures the same idea: a connection whose removal splits a network into separate parts.

Isomorphic graphs

Understanding isomorphism

Different-looking graphs can actually contain exactly the same information. When this happens, we say the graphs are isomorphic or equivalent.

Isomorphic graphs are graphs that contain identical information. They have:

The same number of vertices
The same number of edges
The same connections between corresponding vertices

infoNote

Think of isomorphic graphs as different drawings of the same network. Just as you can draw a square in many orientations or sizes, you can draw the same graph structure in many different ways. The key is that the connection pattern remains identical.

Example of isomorphic graphs

These three graphs look quite different, but they are actually isomorphic. To see why:

Each graph has 4 vertices (labelled $A$ , $B$ , $C$ , $D$ )
Each graph has 5 edges
Corresponding vertices have the same degree. For example, $\text{deg}(A) = 2$ in all three graphs
The edges connect the same pairs of vertices in each graph:
- $A$ to $C$
- $A$ to $D$
- $B$ to $C$
- $B$ to $D$
- $D$ to $C$

Example of non-isomorphic graphs

Although these three graphs all have 4 vertices and appear similar, they are not isomorphic. This is because:

Corresponding vertices do not have the same degree
The edges do not connect the same pairs of vertices across all graphs

chatImportant

Common Mistake to Avoid:

Having the same number of vertices and edges is necessary but not sufficient for graphs to be isomorphic. The pattern of connections must also match.

To verify isomorphism, you must check:

Same number of vertices ✓
Same number of edges ✓
Same degree sequence (all vertices have matching degrees) ✓
Same connection pattern (edges connect corresponding vertex pairs) ✓

Worked example: Identifying bridges and isomorphic graphs

lightbulbExample

Worked Example: Analyzing Graph Properties

Question: Consider the three graphs shown above.

a) Which of the three graphs are connected?

b) Graph 2 contains two bridges. Identify the bridges.

c) Two of the graphs are isomorphic. Identify the isomorphic graphs.

Solution:

Part a: Identifying connected graphs

In each of the three graphs, every vertex is connected to every other vertex, either directly or indirectly through another vertex.

Answer: All three graphs are connected.

Part b: Identifying bridges in Graph 2

To find bridges, we look for edges whose removal would disconnect the graph.

First bridge: Edge $DE$

If we remove the edge between vertices $D$ and $E$ , the graph becomes disconnected. Vertex $D$ will no longer be connected to any other vertices.

Second bridge: Edge $EB$

If we remove the edge between vertices $E$ and $B$ , the graph also becomes disconnected. Vertices $D$ and $E$ will no longer be connected to vertices $A$ , $B$ , and $C$ .

Answer: The two bridges are $DE$ and $EB$ .

Part c: Identifying isomorphic graphs

Step 1: Check if all three graphs have the same number of vertices and edges.

All three graphs have 5 vertices
However, Graphs 1 and 3 have 6 edges, whereas Graph 2 has only 5 edges

Since Graph 2 has a different number of edges, it cannot be isomorphic to the other graphs.

Step 2: Check if the edges connect to the same vertices.

For Graphs 1 and 3, all edges connect to the same vertices:

$DE$ (appears twice - a multiple edge)
$BE$
$BC$
$AB$
$AC$

Answer: The two isomorphic graphs are Graph 1 and Graph 3.

Adjacency matrices

What is an adjacency matrix?

Matrices provide a compact, numerical way to represent graph information, which is particularly useful for computer processing.

Adjacency matrix: An adjacency matrix is a square matrix that uses zero or a positive integer to record the number of edges connecting each pair of vertices in a graph.

infoNote

Adjacency matrices are especially powerful for:

Storing graph data in computer programs
Performing mathematical operations on graphs
Analyzing large networks using linear algebra
Finding paths and patterns efficiently

Structure of an adjacency matrix

Key features:

The matrix is square (same number of rows as columns)
Each row and column represents a vertex
The number at position (row, column) indicates how many edges connect those two vertices
A zero means no direct edge connects those vertices
Loops (edges from a vertex to itself) appear on the diagonal

For the graph and matrix shown above:

The '0' in row $A$ , column $A$ means no edges connect vertex $A$ to itself
The '1' in row $B$ , column $A$ means one edge connects vertex $A$ to vertex $B$
The '2' in row $D$ , column $A$ means two edges connect vertex $A$ to vertex $D$
The '1' in row $C$ , column $C$ means one edge connects vertex $C$ to itself (a loop)

chatImportant

Symmetry Property:

Adjacency matrices are symmetric for undirected graphs because an edge from $A$ to $B$ is the same as an edge from $B$ to $A$ .

This means: entry at position $(i, j)$ = entry at position $(j, i)$

This symmetry property is useful for verifying your matrix is correct!

Worked example: Drawing a graph from an adjacency matrix

lightbulbExample

Worked Example: Constructing a Graph from its Matrix

Question: Draw the graph represented by the following adjacency matrix.

	$A$	$B$	$C$	$D$	$E$
$A$	$0$	$0$	$2$	$0$	$1$
$B$	$0$	$0$	$2$	$1$	$0$
$C$	$2$	$2$	$0$	$1$	$0$
$D$	$0$	$1$	$1$	$1$	$0$
$E$	$1$	$0$	$0$	$0$	$0$

Solution:

Step 1: Draw a dot for each vertex and label them $A$ to $E$ .

Step 2: Starting with row $A$ , look for non-zero entries.

Row $A$ has a '2' in column $C$ and a '1' in column $E$ .

This means vertex $A$ has three edges:

Two edges connecting to vertex $C$
One edge connecting to vertex $E$

Draw these edges.

Step 3: Continue this process row by row until all edges are drawn.

Important notes:

The '1' in row $D$ , column $D$ represents a loop (an edge connecting vertex $D$ to itself)
Since the matrix is symmetric, you only need to process each pair of vertices once
Multiple edges between the same pair of vertices are shown as parallel edges or curves

The final graph shows all vertices and their connections as specified by the adjacency matrix.

Summary of key concepts

bookmarkSummary

Key Concepts to Remember

Connected graphs:

A graph is connected if every vertex can be reached from every other vertex along a series of adjacent edges
If even one pair of vertices has no path between them, the graph is disconnected

Bridges:

A bridge is a single edge in a connected graph that, if removed, leaves the graph disconnected
A graph can have more than one bridge
Bridges are critical connections in networks and represent vulnerable points

Isomorphic graphs:

Graphs are isomorphic if they have the same numbers of edges and vertices
Additionally, corresponding vertices must have the same degree
The edges must connect the same vertices in both graphs
Isomorphic graphs contain identical information but may look different

Adjacency matrices:

An adjacency matrix summarises graph information numerically
There is one row and one column for each vertex
Entries show the number of edges connecting each pair of vertices
A loop (edge from a vertex to itself) is counted as one edge in the matrix
The matrix is symmetric for undirected graphs

Remember!

bookmarkSummary

Essential Takeaways

Connected graphs: Every vertex can reach every other vertex through a path of edges. Check connectivity by verifying all vertices are accessible from any starting point.
Bridges are critical: Removing a bridge disconnects the graph - these are vulnerable points in networks that need special attention in network design.
Isomorphic graphs: Look different but contain identical information - same vertices, edges, and connection patterns. Visual appearance doesn't determine equivalence!
Adjacency matrices: Provide a numerical representation perfect for computer processing. They allow us to use mathematical operations and algorithms on graphs.
Matrix symmetry: For undirected graphs, the adjacency matrix is always symmetric - entry at row $i$ , column $j$ equals entry at row $j$ , column $i$ . Use this property to check your work!

Isomorphic (Equivalent) Connected Graphs and Adjacency Matrices (VCE SSCE General Mathematics): Revision Notes