Course contentsShow
← Mathematics
Lesson 2659 of 3,12153. Graph TheoryFree lesson

Connected Graphs

Define graph connectivity; determine when a graph is connected and identify connected components.

Connected Graphs

You'll learn how to determine whether any two vertices in a graph can reach each other, and how to break a graph into its separate "islands."

What Is Graph Connectivity?

A graph is connected if there exists a path between every pair of vertices. In other words, you can travel from any vertex to any other vertex by following edges—no vertex is isolated or unreachable.

Think of it like a road network: if you can drive from any town to any other town using the available roads, the network is connected. If some towns are cut off with no roads leading to them, the network is disconnected.

Disconnected Graphs and Connected Components

If a graph is not connected, it's called disconnected. A disconnected graph splits naturally into separate pieces called connected components.

Each connected component is a maximal connected subgraph—meaning it's connected internally, and you can't add any more vertices from the graph without breaking that connectedness.

For example, imagine a graph with vertices {A, B, C, D, E} where:

  • A connects to B
  • C connects to D and E
  • No edges link {A, B} to {C, D, E}

This graph has two connected components: {A, B} and {C, D, E}.

How to Determine Connectivity

To check if a graph is connected:

  1. Pick any starting vertex
  2. Perform a walk/traversal (following edges) to visit all reachable vertices
  3. If you've visited all vertices in the graph, it's connected
  4. If some vertices remain unvisited, the graph is disconnected

You can repeat this process starting from unvisited vertices to identify all connected components.

Key Takeaway: A graph is connected if a path exists between every pair of vertices; otherwise, it breaks into separate connected components representing isolated subgraphs.