42

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..

patang
  • 797
  • 1
    Consider an induced subgraph, and then remove some of its edges. Is it still an induced subgraph? Is it a subgraph? – Tuomo Lempiäinen Nov 09 '14 at 11:31
  • 1
    An INDUCED subgraph has the same edges as the original graph between the given set of vertices. A minor is, for example, a subgraph, but in general not an induced subgraph. An important difference is the merging of vertices, for example, a chain u-v-w can be replaced by u-w. If u and w are not connected in the original graph, such a subgraph would be not induced. – Peter Nov 09 '14 at 11:37
  • @Peter can you just elaborate your example as I don't know what a minor is ? – patang Nov 09 '14 at 11:40
  • 2
    Suppose, u and w are the only neighbours of v. Then, replacing the edges u-v and v-w by a single edge u-w produces a MINOR. A minor is a graph that can be constructed by the original graph by deleting vertices, deleting edges or merging vertices as shown. If the edge u-v does not exist in the original graph, the subgraph is not induced. – Peter Nov 09 '14 at 11:46
  • @Peter I don't get in which case can we merge vertices: in induced subgraph or subgraph – patang Nov 09 '14 at 11:47
  • 1
    Merging vertices does not produce an indeced subgraph in general, but it produces a subgraph. – Peter Nov 09 '14 at 11:49
  • @Peter I'm pretty confused by this name 'induced' ,what induction does this subgraph does... – patang Nov 09 '14 at 11:53
  • Maybe, I am wrong with the expression subgraph in case of minors. But what is true, that a general subgraph can have less edges between the given vertex-set than the original graph. – Peter Nov 09 '14 at 12:00

4 Answers4

58

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.

Jan Hrcek
  • 219
Peter
  • 84,454
  • but shouldn't the last line be :"an induced subgraph cannot be constructed by deleting vertices" – patang Nov 09 '14 at 12:14
  • No, the vertices are deleted, the vertex-set of H is, in general, a proper subset of V. – Peter Nov 09 '14 at 12:18
  • @but I don't understand the meaning of incident edges in: "(and with them all the incident edges)but no more edges"....Please help.. – patang Nov 09 '14 at 12:20
  • 2
    The edges incident with a vertex are simply the edges having the vertex as an endpoint. – Peter Nov 09 '14 at 12:20
  • 1
    The edges of the REMAINING vertices are not allowed to be deleted, but deleting a vertex, of course, deletes the edges ending in this vertex. – Peter Nov 09 '14 at 12:23
  • in definition of induced subgraph as given in question it is:"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$." .. shouldn't it be $V$ insetad of $U$ ... – patang Nov 09 '14 at 13:06
  • No, $U$ is the (in general proper) subset of $V$ and the vertex set in $H$ is only $U$, not $V$. – Peter Nov 09 '14 at 13:09
  • but as it says:"If F consists of all edges of G which have endpoints in U" ,where does it says that that edges are adjacent.. – patang Nov 09 '14 at 13:13
  • You mean the vertices ? They do not need to be adjacent in $G$, but if they are not, they are also not adjacent in $H$. To make it simpler : The edges with endpoints in $U$ are the edges remaining, if all vertices but those in $U$ are deleted. – Peter Nov 09 '14 at 13:17
  • the definition of your answer is understandable ,but I can't understand the one given in the question....what's relation between both of them...please help it seems to be confusing.. – patang Nov 09 '14 at 13:27
  • Perhaps, an example helps : Suppose, the edges are $1-2,1-3,2-4,2-5,3-5$ and $U=${$1,2,3$}. The edges between the vertices in $U$ are $1-2,1-3$, so $H$ contains exactly these edges. The edges $2-4,2-5,3-5$ do not occur in $H$ because the vertices $4,5$ do not belong to $U$. – Peter Nov 09 '14 at 13:33
  • 1
    Ah, now I see what you mean. The edge $2-4$ has an endpoint in $U$, is this the problem ? – Peter Nov 09 '14 at 13:35
  • yes I meant that like in this case ,the edge maynot belong in $H$ but has an endpoint in it... – patang Nov 09 '14 at 13:37
  • 1
    Probably, it is meant that BOTH endpoints must belong to $U$, then everything is all right. Otherwise, the formulation would probably be : with at least one endpoint in $U$. – Peter Nov 09 '14 at 13:38
  • 1
    ah ..seems to be clear now...thanks. – patang Nov 09 '14 at 13:43
5

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.

user3492040
  • 51
2

Let G(V, E) be a graph and U is subset of V. For a induced subgraph, say H(U, F) we proceed as

  1. 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.

  2. 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

M. Javaid
  • 31
2

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

  1. $V' \subseteq V$
  2. $E' \subseteq E$
  3. $\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.
Divesh Kumar
  • 21