I have the following paragraph in my notes:
If $G=(V,E)$ is a general graph . Let $U\subseteq V$ and let $F$ be a subset of $E$ such that the vertices of each edge in $F$ are in $U$ ,
then $H=(U,F)$ is also a general graph and $H$ is a subgraph of $G$ .If $F$ consists of all edges of $G$ which have endpoints in $U$ ,then $H$ is called induced subgraph of $G$ and is denoted by $G_U. $
From here both the definition of a subgraph and a induced subgraph seem same to me..
I can't understand what is the difference between them...
Please help with this..
4 Answers
$\begingroup$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.
$\endgroup$ 15 $\begingroup$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.
$\endgroup$ $\begingroup$Let G(V, E) be a graph and U is subset of V. For a induced subgraph, say H(U, F) we proceed as
Collect all possible subgraphs, say $H_1(U, F_1)$, $H_2(U, F_2)$ ,..., $H_n(U, F_n)$ of the graph G fixing set of vertices U in $H_i$, where $F_1, F_2,...,F_n$ are subsets of E.
Find F=max${F_1, F_2,...,F_n}$
Thus, $H(U, F)=\max\{H_1(U, F_1), H_2(U, F_2) ,..., H_n(U, F_n)\}$ is a induced subgraph of the graph G with respect to U.
M. Javaid
$\endgroup$ $\begingroup$Say you have a graph $G(V,E,\phi)$ now any graph $G'(V',E',\phi')$ can be a sub-graph of G only if it satisfies all the 3 conditions
- $V' \subseteq V$
- $E' \subseteq E$
- $\phi'(e)=\phi(e)$ for all e belonging E' While for constructing an induces subdigraph you first take a subset say W of vertex set V, then draw all the edges that lie between all those vertices(unlike a subgraph here you don't have the option to not chose an edge) be careful not to choose an edge that has one vertex in W but one not belonging to W.
