Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

1 Answer

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|improve this answer
    
Thank you Austin! –  haytham abutair Nov 18 '12 at 19:18
add comment

Your Answer

 
discard

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.