subgraphs

Question

number  of subgraph for K3 is

Answer 1

18

Subgraph of a graph is a graph whose vertex set is a subset of vertex set of the graph and edge set is a subset of the edge set of the graph

1)no vertex,no edge : 1

2)one vertex : 3C1=3

3)two vertices(edge present/not present) : 3C2*2

4)three vertices , no edge : 1

5)3 vertices 1 edge : 3C1=3

6)3 vertices 2 edges : 3C2=3

7)3 vertices 3 edges : 1

Adding these up : 18

Answer 2

I think it should be 17

(with at least one vertex)

And asked about  exactly with 3 vertices then 2n(n−1)/2=8

But here  at least  1

vertex so

• 3 subgraph as consider single - vertices ( question does not mention about distinct so we will consider all cases )

• 3 subgraph consider 2 vertices 
• 1 subgraph consider 3 vertices
• 3 subgraph consider  2 vertices, one edge
• 3 subgraph consider 3 vertices, 2edges
• 3 subgraph consider 3 vertices, 1edge
• 1 subgraph consider 3 vertices, 3edges  
•  
•    
• So, total 17

Answer 3

four possible subgraphs

.1 subgraph each for 0,1,2,3 edges.

Answer 4

The answer would be 17 in case of labelled graph .

• with 1 vertex = $_{1}^{3}\textrm{C}$
• with 2 vertices (null graph ) = $_{2}^{3}\textrm{C}$
• with 2 vertices (not null graph ) = $_{2}^{3}\textrm{C}$
• with 3 vertices (null graph ) = $_{3}^{3}\textrm{C}$
• with 3 vertices 1 edge  = $_{3}^{3}\textrm{C} * _{1}^{3}\textrm{C}$
• with 3 vertices 2 edge  = $_{3}^{3}\textrm{C} * _{2}^{3}\textrm{C}$
• with 3 vertices 3 edge  = $_{3}^{3}\textrm{C} * _{3}^{3}\textrm{C}$

and 7 in case of unlabelled graph .

• with 1 vertex = 1
• with 2 vertex = 2
• with 3 vertex = 4

P.S : In definition of graph , although the edge set E may be empty , the vertex set V must not be empty; otherwise there is no graph . - Narsingh Deo Pg-9

https://gateoverflow.in/2443/gate1994_1-6-isro2008-29