Difference between a sub graph and induced sub graph.

A subgraph $H$ of $G$ is called INDUCED, if for any two vertices $u,v$ in $H$, $u$ and $v$ are adjacent in $H$ if and only if they are adjacent in $G$.

In other words, $H$ has the same edges as $G$ between the vertices in $H$.

A general subgraph can have less edges between the same vertices than the original one.

So, an induced subgraph can be constructed by deleting vertices (and with them all the incident edges), but no more edges. If additional edges are deleted, the subgraph is not induced.


For an original graph G(V, E), select set of nodes V' from V. All the existing edges E' that connect between nodes in V' must remain.

This subgraph G' is called induced subgraph.

If you continue to remove some edge from E', then G' is still a subgraph of G, but no longer an induced subgraph of G.

Tags:

Graph Theory