Definition:Induced Subgraph
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
There are no source works cited for this page. Source citations are highly desirable, and mandatory for all definition pages. Definition pages whose content is wholly or partly unsourced are in danger of having such content deleted. To discuss this page in more detail, feel free to use the talk page. |