Undirected Subgraphs

Why

We look at a particular subset of vertices and the edges involved between them.

Definition

Suppose $\mathcal{G} = (V, E)$ is an undirected graph. An undirected graph $(V', E')$ is a subgraph of $\mathcal{G} $ if $V' \subset V$ and $E \subset E'$. The vertex-induced subgraph of an undirected graph $(V, E)$ induced by a subset of vertices $W \subset V$ is the undirected graph with vertices $W$ and all edges between vertices in $W$. The edge-induced subgraph of an undirected graph $(V, E)$ induced by vertices $F \subset E$ whose edge set is $F$ and whose vertices are those vertices adjacent to the edges of $F$.

Notation

Let $W \subset V$ and define $F$ by

\[ F = \Set*{\set{v, w} \in E}{v, w \in W}. \]

The subgraph induced by $W$ is the undirected graph $(W, F)$.

Some authors denote the subgraph induced by $W$ by $G(W)$ or $(W, E(W))$ or $G[W]$. We avoid this notation, as it abuses $G$, which is no longer an ordered pair, but (in our standard function notation) now indicates a function on subsets of $V$ with a complicated codomain. Other authors occasionally refer to the “subgraph $W$”, instead of “the subgraph $G(W)$”. Again, we avoid this practice.

For $D \subset E$, the subgraph induced by $D$ is the undirected graph $(U, D)$ where

\[ U = \Set{v \in V}{\exists e \in D: x \in e} \]

Simiarly, people write $G(D)$ or $(V(D), D)$. We avoid this.

Connected components

A set of vertices $W$ in $G$ is connected if there is a path between any two vertices $v, w \in W$. A set of vertices $W$ in $G$ is maximimally connected if there is no other vertex $v \not \in W$ connected to a vertex in $W$. A connected component of $G$ is the subgraph induced by a maximally connected set of vertices.

Since the vertex set of a graph can always be partitioned into sets maximally connected vertices, and a connected components is connect, we think of the connected components of $G$ as the connected “pieces” of $G$.

Cliques

A set of vertices is complete if the subgraph induced is complete. A set of vertices $W$ is maximally complete if the subgraph induced is complete and there is no vertex $v \not\in W$ which is connected to every vertex in $W$. In other words, there is no other vertex which we can add to $W$ so that the induced subgraph is still complete.

We call a maximally complete set of vertes a clique. Some authors define a clique in the way we have defined a complete set of vertices, without reference to the maximality.