Combinatorics • Topic 29
Connectedness
A fundamental property of graphs is whether they are "in one piece."
Definitions
- Connected: There is a path between every pair of vertices.
- Connected Component: A maximal connected subgraph.
- Cut Vertex: A vertex whose removal increases the number of components.
- Bridge: An edge whose removal increases the number of components.
Connectivity Bounds
Theorem
A graph with vertices and components has at least edges.
Theorem
A graph with vertices and more than edges is connected.
Practice Problems
Exercise (Problem 1)
Prove that if is not connected, then its complement is connected.
Exercise (Problem 2)
What is the minimum number of edges required to ensure a graph with vertices is connected?
Exercise (Problem 3)
Find the maximum number of edges in a disconnected graph with vertices.