Connectivity in Graph Theory II

students, imagine a city map where some neighborhoods are linked by roads and others are not 🚗🌉. In graph theory, that idea becomes connectivity: can you get from one vertex to another by following edges? This lesson explains the main language of connectivity, shows how to test whether graphs are connected, and connects the idea to the wider study of Graph Theory II, including Euler and Hamilton ideas and bipartite graphs.

What connectivity means

A graph is made of vertices and edges. Vertices are the points, and edges are the links between them. A graph is called connected if, for every pair of vertices, there is a path between them. A path is a sequence of edges that lets you move from one vertex to another without “jumping.”

If a graph is not connected, then it has two or more separate parts called connected components. Each component is a connected graph on its own. You can think of connected components like islands separated by water 🌊. You can travel anywhere on one island, but you cannot reach a different island unless there is a bridge.

A helpful way to state the idea is:

$$\text{A graph is connected if every vertex is reachable from every other vertex.}$$

For example, suppose a social network graph has people as vertices and friendships as edges. If one student can reach another through a chain of friendships, the two are in the same connected component. If there are people who have no chain connecting them to others, the network is disconnected.

Connectivity is one of the first big ideas in Graph Theory II because many later topics depend on it. Before asking whether a graph has an Euler circuit or a Hamilton cycle, we need to know whether the graph is connected enough to make those ideas possible.

How to tell whether a graph is connected

There are two common ways to test connectivity: by looking for paths and by using a traversal process such as depth-first search or breadth-first search. Both methods are based on the same question: can we reach every vertex?

Using paths directly

If you can find a path from one vertex to every other vertex, then the graph is connected. For small graphs, this can be done by inspection. Start at a vertex and trace edges to see where you can go.

Example: imagine vertices $A$, $B$, $C$, and $D$ with edges $AB$, $BC$, and $CD$. Then there is a path from $A$ to $D$:

$$A \to B \to C \to D$$

So the graph is connected.

Now remove the edge $BC$. The graph splits into two parts: one containing $A$ and $B$, and the other containing $C$ and $D$. Now there is no path from $A$ to $D$, so the graph is disconnected.

Using graph search

For larger graphs, checking paths by hand becomes slow. A search method helps. Start at one vertex and mark every vertex you can reach by following edges. If all vertices get marked, the graph is connected. If some are never reached, the graph has more than one component.

This idea is important in computer science too 💻. For example, a map app may use graph search to see whether a route exists between two places, or a computer network may use connectivity checks to see whether all devices can communicate.

Connected components and cut edges

When a graph is disconnected, its parts are called connected components. Each component is a maximal connected subgraph, meaning you cannot add any more vertices from the original graph without losing connectivity inside that part.

Consider a graph with two triangles that are not connected to each other. Each triangle is one connected component. If there were a bridge edge connecting the triangles, the whole graph would become connected.

A very important idea is a cut edge or bridge. A bridge is an edge whose removal increases the number of connected components. In simple terms, if removing one road cuts off part of a city, that road is a bridge in the graph model.

Example: suppose a graph is a line of vertices $P$, $Q$, $R$, $S$ with edges $PQ$, $QR$, and $RS$. Every edge here is a bridge. If you remove $QR$, the graph breaks into two components:

one containing $P$ and $Q$
one containing $R$ and $S$

Bridges matter because they show fragile points in a network. A road closure, a broken cable, or a missing link can disconnect the whole system.

Why connectivity matters for Euler and Hamilton ideas

Connectivity is closely related to the other topics in Graph Theory II.

Euler ideas

An Euler trail is a path that uses every edge exactly once. An Euler circuit is an Euler trail that starts and ends at the same vertex. For a graph to have an Euler circuit, it must be connected in the part of the graph that contains edges, and every vertex must have even degree.

The connectivity condition is necessary because if the graph has separate parts, one walk cannot cover edges in different components without teleporting 🧭. So connectivity is part of the setup before checking degree conditions.

Hamilton ideas

A Hamilton path visits every vertex exactly once, and a Hamilton cycle is a Hamilton path that returns to the starting vertex. Connectivity is also important here because a disconnected graph cannot have a Hamilton cycle. If the graph has separate components, there is no way to visit all vertices in one cycle.

However, connectivity alone does not guarantee a Hamilton cycle. A graph may be connected and still fail to have one. So connectivity is necessary in many cases, but not always sufficient.

This shows why connectivity is a foundation topic: it helps determine whether more advanced graph properties are even possible.

Connectivity and bipartite graphs

A bipartite graph is a graph whose vertices can be split into two sets so that every edge goes from one set to the other, never within the same set. Bipartite graphs are often connected, but they do not have to be.

For example, a disconnected bipartite graph might consist of two separate trees. Each tree can be bipartite, and the whole graph can still be disconnected.

Connectivity helps us understand how bipartite graphs behave. A connected bipartite graph has a very useful structure: you can often color its vertices with two colors so that adjacent vertices always get different colors. This is called 2-coloring.

Example: if a graph represents students and clubs, and edges show membership relationships that must alternate between two types, then bipartite structure may appear naturally. If the graph is connected, all vertices are part of one network of relationships, making analysis easier.

A famous fact is that a graph is bipartite if and only if it has no odd cycle. Connectivity is not the deciding factor here, but it helps when studying cycles inside one component.

Examples and reasoning practice

Let’s look at a few clear examples.

Example 1: A connected graph

Vertices: $1$, $2$, $3$, $4$

Edges: $12$, $23$, $34$, and $24$

From $1$ you can reach $2$, then $3$, then $4$. So every vertex is reachable from every other vertex. The graph is connected.

Example 2: A disconnected graph

Vertices: $a$, $b$, $c$, $d$, $e$

Edges: $ab$, $bc$, and $de$

Here, $a$, $b$, and $c$ form one component, while $d$ and $e$ form another. There is no path from $a$ to $d$, so the graph is disconnected.

Example 3: A bridge creates disconnectivity

Suppose a graph has two dense clusters connected by exactly one edge. That edge is a bridge. If it is removed, the graph becomes disconnected. This is common in transportation or communication networks where one weak link connects two major systems.

Reasoning tip

To decide whether a graph is connected, do not just count edges. A graph with many edges may still be disconnected if the edges stay inside separate groups. Instead, focus on reachability: can you move from each vertex to every other vertex?

Conclusion

Connectivity asks a simple but powerful question: can every vertex reach every other vertex by following edges? students, this idea is a core building block of Graph Theory II because it helps describe graph structure, find components, identify bridges, and prepare for Euler and Hamilton topics. It also connects naturally to bipartite graphs and graph coloring. In real networks such as roads, friendships, and computers, connectivity shows whether the system works as one unit or breaks into separate pieces. Understanding connectivity gives you the tools to reason about larger graph problems with confidence ✅

Study Notes

A graph is connected if there is a path between every pair of vertices.
If a graph is not connected, it has two or more connected components.
A bridge or cut edge is an edge whose removal increases the number of components.
To test connectivity, try to reach every vertex from one starting point.
Depth-first search and breadth-first search are common ways to check reachability in large graphs.
Connectivity is important for Euler trails and Euler circuits because a walk cannot cover separate components.
A disconnected graph cannot have a Hamilton cycle.
Bipartite graphs can be connected or disconnected; connectivity is separate from bipartiteness.
A graph is bipartite if and only if it has no odd cycle.
Real-world examples of connectivity include road networks, friendship networks, and communication systems.