Definition:Induced Subgraph

From ProofWiki
Jump to navigation Jump to search

Definition

Let $G = \struct {\map V G, \map E G}$ be a graph.

Let $V' \subseteq V$ be a subset of vertices of $G$.


The subgraph of $G$ induced by $V'$ is the subgraph $G' = \struct {\map {V'} {G'}, \map {E'} {G'} }$ of $G$ such that:

$G'$ has the vertex set $V'$
For all $u, v \in V'$, $e = u v \in \map E G$ if and only if $e \in \map {E'} {G'}$.


That is, it contains all the edges of $G$ that connect elements of the given subset of the vertex set of $G$, and only those edges.


Sources