I'm a little confused on the part of "induced" does this mean that from the set of vertices and set of edges that are given, that every vertex is connected to every other vertex? Or for instance, what if I have a set of vertices and a set of edges but one of the vertices is not connected to any other vertex. Would this be considered a graph? or even more specific an induced graph? Thank you

Also, can these subgraphs contain cycles?


A subgraph of $G$ is just any subset of $V(G)$ and any subset of $E(G)$ that is itself a graph. For example, the cycle on six vertices is a subgraph of the complete bipartite graph on eight vertices (choose three vertices from each partite set and the appropriate edges to form a cycle).

An induced subgraph is any subset $S$ of $V(G)$ with edge set $$ \{uv \mid u,v \in S \text{ and } uv \in E(G)\}. $$ In words, you choose only the vertex set for your induced subgraph and then an edge will connect two of those vertices in the induced subgraph if and only if it was present in the original graph. For example, if we choose the same six vertices as in the previous example, the induced subgraph must be the complete bipartite graph on six vertices. We have no freedom to leave out any edges as we did with subgraphs. We must take all and only those edges present between the specified vertices.

  • $\begingroup$ Nice answer Austin, do you know about indicator functions about induced subgraphs? I have tried to find information about them but cannot find, asked here. $\endgroup$ – hhh Jul 9 '16 at 17:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.