Graph Theory Lessons
Lesson 35:
Vertex Connectivity
A vertex v in a connected graph is an articulation point if the removal of v and all edges with v as an end-point from the graph would leave a disconnected graph.
In some literature a vertex is considered to be an articulation point if its removal would increase the number of connected components of the graph. Do you see why this is a different definition? We shall use the first one.
Java Web Start Activity:
In the Java Web Start application below, draw a graph in the left
pane. If the graph is connected, any articulation points will have a
circle drawn around them. A list of the connected components and
articulation points of the graph will be printed in the right pane.
Removing any of the articulation points would disconnect the graph.
Use the Petersen program to help you answer the following questions. The menu item for articulation points is Properties | Connectivity | Articulation Points.
- 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 connected graph G with more than two vertices 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.
Suppose you have a connected graph. You might wonder how many vertices you would need to remove in order to disconnect the graph. A set of vertices whose removal would disconnect the graph is called a vertex cut. Typically a graph will have many vertex cuts. The vertex connectivity of a graph is the size of its smallest vertex cut(s). Often the vertex cut that achieves this minimum is not unique. If the vertex connectivity of a graph of a graph is k, then we say the graph is k-vertex connected. The complete graphs do not have vertex cuts. By convention a complete graph on n vertices is considered to be (n - 1)-vertex connected.
Java Web Start Activity:
In the Java Web Start application below, draw a graph in the left
pane. If the graph is connected, the vertices that form a smallest
vertex cut will have a circle drawn around them. Removing all the vertices of
the vertex cur would disconnect the graph.
- Find a graph with exactly one vertex cut.
- What is the vertex connectivity of the complete bipartite graph Kr, s?
- What is the vertex connectivity of the complete tripartite graph Kr, s, t?
- If the vertex of lowest degree in a graph has degree d why must its vertex connectivity be less than or equal to d? Draw an example where the vertex connectivity is less than d.
- Draw a graph that is regular of degree 3 and yet 2-vertex connected.
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.
Java Web Start Activity:
In the Java Web Start application below, draw a graph in the left
pane. The application will tell you if the graph is strongly or
weakly connected.
Answers
© C. Mawata
