42
$\begingroup$

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

$\endgroup$
8
  • 1
    $\begingroup$ Consider an induced subgraph, and then remove some of its edges. Is it still an induced subgraph? Is it a subgraph? $\endgroup$
    – Tuomo Lempiäinen
    Commented Nov 9, 2014 at 11:31
  • 1
    $\begingroup$ 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. $\endgroup$
    – Peter
    Commented Nov 9, 2014 at 11:37
  • $\begingroup$ @Peter can you just elaborate your example as I don't know what a minor is ? $\endgroup$
    – patang
    Commented Nov 9, 2014 at 11:40
  • 2
    $\begingroup$ 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. $\endgroup$
    – Peter
    Commented Nov 9, 2014 at 11:46
  • 1
    $\begingroup$ Merging vertices does not produce an indeced subgraph in general, but it produces a subgraph. $\endgroup$
    – Peter
    Commented Nov 9, 2014 at 11:49

4 Answers 4

Reset to default
58
$\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
  • 2
    $\begingroup$ The edges incident with a vertex are simply the edges having the vertex as an endpoint. $\endgroup$
    – Peter
    Commented Nov 9, 2014 at 12:20
  • 1
    $\begingroup$ 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. $\endgroup$
    – Peter
    Commented Nov 9, 2014 at 12:23
  • 1
    $\begingroup$ Ah, now I see what you mean. The edge $2-4$ has an endpoint in $U$, is this the problem ? $\endgroup$
    – Peter
    Commented Nov 9, 2014 at 13:35
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Peter
    Commented Nov 9, 2014 at 13:38
  • 1
    $\begingroup$ ah ..seems to be clear now...thanks. $\endgroup$
    – patang
    Commented Nov 9, 2014 at 13:43
5
$\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$
2
$\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

  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

$\endgroup$
2
$\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

  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.
$\endgroup$
1
  • 1
    $\begingroup$ Hi! Welcome to MSE. Please use MathJax to format your answer so that it's much easier to understand $\endgroup$
    – Ankit Kumar
    Commented Jan 21, 2019 at 17:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .