How many induced subgraph of a graph on n vertices?

Question

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.

Answer 1

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.