The Gateway to Computer Science Excellence
+2 votes

Number of subgraphs possible for K3 =____________

in Graph Theory by Veteran (119k points) | 195 views
7 unlableled subgraphs.
for unlabeled subgraphs, there is no formula,

you have to find it manually.

but ans for K3=17


i have given answer for unlabeled graphs,

17 is for labeled graph.

it should be mentioned in qsn that graph is labeled.
its assumed that graphs are not labeled

2 Answers

+1 vote
Best answer

  • 33 subgraph as consider single - vertices ( question does not mention about distinct so we will consider all cases )
  • 33 subgraph consider 22 vertices 
  • 11 subgraph consider 33 vertices
  • 33 subgraph consider  22 vertices, one edge
  • 33 subgraph consider 33 vertices, 22 edges
  • 33 subgraph consider 33 vertices, 11 edge
  • 11 subgraph consider 33 vertices, 33 edges

So, total 17

by Active (4.2k points)
selected by
$\sum_{r=1}^{n}\binom{n}{r}$2^r*(r-1)/2 applying this formula  3+6+8>>17 ans rest what is said by joshi nitish
@Akshat Sharma ,can u please give some reference regarding this  formula ?
+2 votes

Subgraph G'(V',E') of a graph G(V,E) is when V'⊆V and E'⊆E.

Let G has 3 vertices A,B and C.

Subgraphs with one node:

V'={A} and E'=null. There can be 3 such graphs.

Subgraphs with two nodes but no edges:

V'={A,B} and E'=null. There can be 3 such graphs V'={B,C} and {C,A}.

Subgraphs with two nodes and one edge:

V'={A,B} and E'={AB}. 3 such cases.

Subgraphs with 3 nodes and no edge.

V'={A,B,C} and E'=null. 1 case.

Subgraphs with 3 nodes and one edge.

V'={A,B,C} and E'={AB}. Again 3 cases.

Subgraphs with 3 nodes and two edges.

V'={A,B,C} and E'={AB,BC}. 3 cases.

Subgraphs with 3 nodes and 3 edges.

V'={A,B,C} and E'={AB,BC,CA}. 1 such case.

Total subgraphs = 5*3+1+1 =17.

by Boss (23.5k points)
Manually is better but carefully check all possible case

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,385 answers
105,384 users