1.1 Subgraph

A graph $G^{{\prime}}=\left(V^{{\prime}},E^{{\prime}}\right)$ is a subgraph of $G$ if the following conditions apply.

• $V^{{\prime}}\left(G^{{\prime}}\right)\subset V(G)$.

• $E^{{\prime}}(G^{{\prime}})$ consists of edges $(v,w)$ in $E(G)$ where both $v$ and $w$ are in $V^{{\prime}}(G^{{\prime}})$.

If $E^{{\prime}}(G^{{\prime}})$ consists of all the edges in $E(G)$ for which the second condition holds, then $G^{{\prime}}$ is an induced subgraph of $G$. An induced subgraph of $G$ that is not a proper subset of any other connected subgraph of $G$ is called a connected component of $G$.