Graph Connectivity

Components §

• A component of a graph is a maximally connected subgraph of the particular graph. That is, we cannot add any more vertices and edges to the subgraph. The number of components is denoted
  • (Component-Edge Inequality, Wilson 5.2) - Let be a simple graph with vertices. If has components, then the number of edges satisfies:
    • (Theorem): Let , then
  • (Wilson 5.3) Any simple graph with vertices and more than edges is connected ¹

• Two special cases of components

  • An isolated vertex is a vertex with degree .
  • A component is trivial if it has no edges

• Two vertices are connected if there exists a a path in that connects and . Otherwise they are disconnected vertices.

  • Adjacency is a special case of connectivity.

• A graph is connected if each vertex in the graph is connected. It has only one component otherwise is disconnected

  • (Mesbahi e2.12) If is simple, then and cannot both be disconnected.

Vertex Subsets §

• A clique of is a set of pairwise adjacent vertices. More formally let be a clique of . Then:

• An independent set of the graph is a set of pairwise non-adjacent vertices. More formally, the following holds for independent set

• A neighborhood of a vertex is the set of all vertices that are adjacent to . This is denoted as .

  We can generalize it to a set of vertices . The neighborhood of , denoted is the set of all vertices that are adjacent to a vertex in .

Connectivity §

Vertices §

• A separating set also called a vertex cut, in a connected graph is a set of vertices whose deletion disconnects .

  • In general it is the set of vertices that increase the number of components by .

• A cut vertex is a separating set with only one element.

• If is connected, its vertex connectivity, denoted is the size of the smallest separating set in .

  It is the minimum number of vertices we need to delete to disconnect .

  If , we say the graph is -connected

Edges §

• Disconnecting set in a connected graph is a set of edges whose removal disconnects .
  • In general, a disconnecting set increases the number of components.
• A cut-set is a disconnecting set such that no proper subset of it is a disconnecting set.
  • (Wilson e5.11b) If two distinct cut-sets of contain an edge , then has a cut-set that does not contain ²

• A bridge is a cut-set with only one edge.

  • (Theorem): If is a bridge, then it appears in every spanning forest.
    • If it didn’t then the spanning forest would not be able to cover all vertices since removing it disconnects the graph.

• Let be a connected graph. The edge connectivity of , denoted is the size of the smallest cut-set in .

  It is the minimum number of edges we need to delete to disconnect .

  If , we say that is -edge connected

General Connectivity §

• (Bondy and Murty 3.1) Connectivity Inequality If is a connected graph, then

  In fact, we can analyze this inequality using the Laplacian

• Graphs and are disjoint if they have no vertices in common

• Graphs and are edge disjoint if they have no edges in common

Biconnectivity and Blocks §

• A graph is biconnected if it is -connected

• A connected graph that has no cut vertices is called a block.

• A biconnected component is a maximal biconnected subgraph.

• (Bondy and Murty 3.2.1) In a biconnected graph, any two distinct vertices lie in a common cycle.

• (Bondy and Murty 3.2.2) If is a block with , then any two edges of lie on a common cycle.

• Whitney’s Theorem A graph with is biconnected if and only if two vertices of are connected by at least two internally disjoint paths.

Links §

• Fundamental Constructs of Graph Theory
• Families of Graphs
• Operations on Graphs

Footnotes §

1. Substitute to the Component-Edge inequality. ↩

2. Each cut set partitions the graph into and respectively. Clearly and cannot be empty (show this is true). The cut-set and whichever is non-empty is the one we desire. Demonstrate cannot be in this cut-set either ↩