1.1 Subgraph

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

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

  • EGE^{{\prime}}(G^{{\prime}}) consists of edges v,w(v,w) in EGE(G) where both vv and ww are in VGV^{{\prime}}(G^{{\prime}}).

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