📂Graph Theory

Subgraph

Definition ¹

For a given graph $G$, graph $H$ is said to be a subgraph of $G$ if it satisfies $V(H) \subset V(G)$ and $ E(H) \subset E(G)$.

Explanation

It is important not to denote $H$ being a subgraph of $G$ as $H \subset G$. The concept of a subgraph serves not so much as a focus of interest in graph theory itself but rather as a natural and common term.

Examples

By defining a subgraph, the following can be considered as examples:

Component

The components of a disconnected graph $D$ are all subgraphs of $D$.

Graph Subtraction

Given graph $G$:

• For edge: $e \in E(G)$, $E(G) - e$ is defined as the graph with the edge $e$ of $G$ removed, and naturally, it becomes a subgraph of $G$. This operation of graph subtraction $-$ can also be extended to sets of edges. $E(G) - E$ is defined as the graph with the subset of edges $E$ of $G$ removed, and likewise, it becomes a subgraph of $G$.
• For vertex: $v \in V(G)$, $E(G) - v$ is defined as the graph with the vertex $v$ of $G$ and all edges attached to $v$ removed. This can also be extended to sets of vertices. $E(G) - V$ is defined as the graph with the subset of vertices $V$ of $G$ and all their attached edges removed, and naturally, it becomes a subgraph of $G$.
• Graph contraction: Note the symbol $-$ in the two subtraction operations mentioned above. The set subtraction symbol $\setminus$ is used to mean the contraction of an edge in a graph. Contracting an edge means removing the edge $e$ and treating the two endpoints $v$ and $w$ as the same.

Such operations of graph subtraction are very convenient tools when discussing algorithms for constructing graphs, etc.

Spanning

If subgraph $H$ of $G$ satisfies $V\left( H \right) = V(G)$, $H$ is referred to as Spanning of $G$. Simply put, it’s a subgraph where vertices remain as is, but only edges might have been removed. It falls under the case of edge removal in graph subtraction.

Induced Graph

If subgraph $H$ of $G$ satisfies $$ E \left( H \right) = \left\{ uv \in E(G) : u,v \in V \left( H \right) \right\} $$, it is called an Induced Graph. An induced graph, unlike spanning which may have edges removed without a specific rule and thus only vertices preserved, ensures that if vertices are preserved, their connecting edges are preserved as well. Consequently, it can be inferred that the induced graph inherits some properties of the original graph $G$.