Graph theory · Definition

Connected graph

discrete mathematicsgraphs

Before you start you need to know

It tells graphs made of one piece apart from those that split into isolated pieces, and lets us talk about «parts» of a graph.

Definition

A graph \(G=(V,E)\) is connected if any two vertices \(u,v\in V\) are joined by a path.

\[\forall\,u,v\in V\ \ \exists\ \text{path from } u \text{ to } v\]

If a graph is not connected, it decomposes uniquely into connected components: the largest possible connected subgraphs. Two vertices lie in the same component exactly when there is a path between them, and this relation splits the vertices into disjoint classes. A graph is connected when it has a single component; the one-vertex graph is connected.

Counting edges gives a useful bound. A connected graph with \(n\) vertices has at least \(n-1\) edges, because each edge joins at most two components. At the other extreme, a disconnected graph with \(n\) vertices has at most \(\binom{n-1}{2}\) edges (a complete graph on \(n-1\) vertices plus an isolated one); more edges than that force the graph to be connected.

Removing an edge that lies on a cycle does not break connectedness, since the rest of the cycle provides a detour. An edge whose removal does disconnect the graph is called a bridge. A common mistake is to think connected means «having all possible edges»: that is a complete graph, a very special case. Connectedness is the property behind trees, Eulerian tours and distances.

Think about it

Is the graph on 3 vertices with no edges connected?

No: it has 3 components, each a single vertex, and there is no path between distinct vertices.

Exercises 10

  1. A graph has vertices \(1,2,3,4\) and edges \(12\), \(23\), \(34\). Is it connected?
  2. A graph with vertices \(1,\dots,5\) has edges \(12\), \(23\) and \(45\). How many connected components does it have?
  3. A graph with vertices \(1,\dots,6\) has edges \(12\), \(34\) and \(56\). How many connected components does it have?
  4. What is the smallest number of edges a connected graph with 8 vertices can have?
  5. What is the largest number of edges a graph with 6 vertices can have without being connected?
  6. A graph with vertices \(1,\dots,5\) has edges \(12\), \(23\), \(13\) and \(45\). Which of these edges, once added, makes it connected?
  7. A graph with 6 vertices has 11 edges. What can be said?
  8. In the cycle \(1,2,3,4,5,6,1\) (edges \(12,23,34,45,56,61\)) the edges \(12\) and \(45\) are removed. How many connected components remain?
  9. Let \(G\) be a connected graph and \(e\) an edge that lies on a cycle of \(G\). After removing \(e\), the resulting graph is:
  10. How many different connected graphs are there on labeled vertices \(1,2,3,4\)? (Two graphs are different if their edge sets differ.)

References

  • Kenneth H. Rosen, Discrete Mathematics and Its Applications, 8th edition, McGraw-Hill, 2019. §10.4
  • Susanna S. Epp, Discrete Mathematics with Applications, 5th edition, Cengage, 2019. §10.2
  • Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, 5th edition, Pearson, 2003. §11.2