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
Let and . The induced subgraph denoted is defined as

That is, it is the induced subgraph whose vertices are adjacent to some vertex in but are not in . We call the (outer) boundary of or neighborhood of . If then we simply denote the neighborhood by

We can similarly define the edge boundary of the induced subgraph denoted defined as

That is, it is the set of edges where one endpoint is in and the other is not.
- (Godsil 3.3.1) Let , then
  - Proof: Let be the set of edges such that and . Let us find the quantity .
    
    For each term in the inequality, we can express them as follows. The last term in the fourth equation below is negative to account for double counting.
    
    And so we have
The closure of is defined as the union between and its boundary

Similarly, the closure of can be defined as

For convenience, we will use the notation

(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

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.