Subgraphs, Paths, Cycles and Components

Subgraphs

A subgraph of a graph is the graph obtained from it by removing zero or more vertices or edges.

Note: Removing an edge does not result in the removal of its end-vertices. However, removing a vertex necessarily results in the removal of its incident edges.

So, starting with an obvious example—every graph is its own subgraph. A single vertex of a graph $G$ is a subgraph of $G$, as is a single edge of $G$.

We say a graph $G$ is an improper subgraph of $G$. All other subgraphs of $G$, are said to be its proper subgraphs, and are said to be properly contained in $G$. Some examples of proper and improper subgraphs can be seen below:

Let’s take a look at some important types of graphs that occur as subgraphs. These are immensely useful for carrying out discussions of graph algorithms.

Paths

...