Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

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.

share|cite|improve this answer
Thank you Austin! – haytham abutair Nov 18 '12 at 19:18
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. – hhh Jul 9 at 17:01

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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