0

Let $G, G'$ be graphs.

If $G' \subseteq G$ and $G'$ contains all the edges $xy \in E$ with $x,y \in V'$, then $G'$ is an induced subgraph of $G$. We say that $V'$ induces or spans $G'$ in $G$, and write $G'=:G[V']$. Thus if $U \subseteq V$ is any set of vertices, then $G[U]$ denotes the graph on $U$ whose edges are precisely the edges of $G$ with both ends in $U$.

Can I say that the term "induced" brings some sort of equivalence meaning? So that, if some equivalence holds, I can use smaller structures for my convenience. In other words, does the graph $G'$ preserve some sort of structure or properties belonging to graph $G$?

baudo2048
  • 111
  • 1
    The graph $G'$ inherets all edges of $G$ that exist between nodes of $G'$. – Wuestenfux Jul 19 '17 at 10:08
  • 3
    The reason it's called "induced" is that you don't select which edges go into $G'$: once you select which vertices are included in $G'$ then the edges are induced from the selected vertices. There is no deeper meaning beyond that, so you shouldn't assume that a particular property is preserved by the operation unless there is a good reason for it. But it would be reasonable to say something like "a vertex colouring of $G$ induces a colouring of $G'$". – Erick Wong Jul 19 '17 at 11:18
  • thanks @ErickWong your comment let me understand what "induced" means. – baudo2048 Jul 19 '17 at 11:57
  • So, "induced" also means that the choise (or construction) of an induced subgraph is more "restrictive" than a "normal subgraph" because the choise of the edges of the induced subgraph is not (totally) arbitrary because it depends on the choise of the vertex subset. – baudo2048 Jul 20 '17 at 08:42

0 Answers0