[Math] ny difference between an induced sub graph and a partial graph

graph theory

By definitions, both ' induced sub graph ' and ' partial graph' seem to be the same. But these two terms often confuse me as why two different terminologies to mean a same stuff? In the following, $H$ is an induced sub graph (partial graph) of $G$:enter image description here

Edited: A sub graph $G_1=(V_1, E_1)$ of $G_2=(V_2, E_2)$ is called a partial graph of $G_2$ if $E_1$ consists of edges in $G_2$ whose joining vertices are in $V_1$. I found this definition from a source but couldn't get it to cite now.

Best Answer

If $H$ is an induced subgraph of $G$, then part of what that means is that there is is an injection $\alpha$ from $V(H)$ (the set of $H$'s vertices) to $V(G)$, and that for every edge $h_1h_2$ of $H$, $\alpha(h_1)\alpha(h_2)$ is an edge in $G$. But it also means that if $h_1, h_2$ are vertices of $H$ and $H$ does not have an edge $h_1h_2$, then $\alpha(h_1)\alpha(h_2)$ is not an edge in $G$.

IME the adjective "induced" is used before the name of a graph rather than some subgraph $H$ of another graph $G$ with all $H$'s vertices already labelled with some of $G$'s vertices' labels. We use phrases such as "induced 4-cycle" -- which does not presuppose any prior correspondence between the 4-cycle's vertices and 4 of $G$'s vertices.

To come back to your example, $G$ does indeed have an induced copy of your $H$. But consider the statement "$G$ has an induced 4-cycle". It does, but $befc$ would not be an example. This is because $G$ has the edge $ce$, which joins two of the 4-cycle's vertices but is not an edge of that cycle. ($G$ has induced 4-cycles such as $adfe$. For $adfe$ to qualify, not only must $G$ have all its 4 edges, $G$ must also lack edges $af$ and $de$.)

Related Question