Graph Theory Lessons

Lesson 14b: Connectedness

We say that a graph is connected if it cannot be expressed as the union of two graphs; otherwise we say that it is disconnected. A disconnected graph can be expressed as the union of two or more connected subgraphs called components.

If you draw a graph in the applet below you will get a list of the components on the right side of the applet.

If X(G₁)=a and X(G₂)=b, then what is X(G₁ U G₂)? (You might have to do some experiments to give you some ideas)

If X(G₁)=a and X(G₂)=b, then what is X(G₁ + G₂)?

Now suppose you have a connected graph and you remove a vertex and all edges with that vertex as an endpoint. Will the graph that remains be connected? If not then we call the vertex you removed an articulation point. An articulation point of a connected graph is a vertex whose removal disconnects the graph. The applet below will help you grasp the idea of articulation points. If you draw a graph in the applet you will get a list of the articulation points on the right side of the applet.

How many articulation points does a circuit have?

Prove that if a graph has a Hamilton circuit then it has no articulation points

Prove that if a graph G has no articulation points then for each pair of vertices w and v there are at least two distinct paths (with no vertices in common other than the end points) from w to v.

An edge in a connected graph is a bridge if deleting it would create a disconnected graph. If you draw a graph in the applet below you will get a list of the bridges on the right side of the applet.

Another way to look at connectedness is to say that a graph is connected if for all pairs of vertices v and w there is a path from v to w. This is easy to see in an undirected graph. Directed graphs are a little more complicated. If G is a directed graph we say that G is strongly connected if for all pairs of vertices v and w in G there is a path in G from v to w. On the other hand we say that a directed graph is weakly connected if for all pairs of vertices v and w in G there is a path in the underlying undirected graph from v to w.

The applet below will help you see the difference.

e-mail: C. Mawata