I am new to graph theory and I am not sure if I got this correct. I said that there is going to be only one induced subgraph of a graph on n vertices because you have to include all the edges that connect the n vertices.

$2.$ Draw all the subgraphs of $K_{3}$ and find how many are induced subgraph.

For this one I got six subgraphs but I am not sure how many of these are induced subgraph. How do I figure this out? Also if you took the three vertices without any edges connecting them, would you call this a subgraph?

Thank you.

  1. A vertex-induced subgraph (or induced subgraph) is a subset of vertices and all edges whose two endpoints are in the subset. However, the answer to this question is different depending on the context.

    If the graph has only $n$ vertices, then the induced subgraph will be the graph itself. If the graph has more than $n$ vertices, then the induced subgraph of $n$ vertices can be found based on the definition given above.

  2. In terms of $K_3$, the subgraphs are

    1). 1 vertex, no edges. (3 subgraphs)

    2). 2 vertices, no edges. (3 subgraphs)

    3). 2 vertices, 1 edge. (3 subgraphs)

    4). 3 vertices, no edge (1 subgraph)

    5). 3 vertices, 1 edge (3 subgraphs)

    6). 3 vertices, 2 edges (3 subgraphs)

    7). 3 vertices, 3 edges (1 subgraph)

    Depending on the context, if we are only discussing connected graphs, (2), (4), and (5) can then be eliminated.

    By definition, (1), (3), and (7) are induced subgraphs.

  • $\begingroup$ I think rather than "simple graphs", you mean connected, right? $\endgroup$
    – pjs36
    Feb 25 '16 at 15:56
  • $\begingroup$ @pjs36 Yes, Id better say connected graphs. $\endgroup$
    – Ralph Xu
    Feb 25 '16 at 16:03

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.