graph theory

Question

consider a complete bipartite graph K(3,3)

The ratio of total number of possible vertex induced subgraphs to the total number of possible edge induced subgraph in given bipartite graph is x:y .

then value of x+y is______.

Comments

@magma can you explain it more?

---

@Magma @Shaik

can u check here, why C) not ans then? https://gateoverflow.in/954/gate2003-67?fbclid=IwAR0B2GHuQQvz2u5Q5NKLni4P5Grh_5Q_32Wo6Oji93qoinlkY02WCIc8-Z0

@Magma what u mean by 

pairwise adjacent vertices

---

for explanation I take the image  from the comments section  the link you provided

Now ,

cliques of Graph G = {A,B,C}  {C,D}  {D,E}

cliques in Graph G1 = {A,B} and {D,E}

then how V1 forms a Clique in G ???

Answer 1

SUB-GRAPH  : A sub-graph of G is a graph H such that V(H)  $\subseteq$ V(G) and E(H)  $\subseteq$ E(G)

In general , Normal Sub-graph is obtain by either you delete vertices or you delete Edges or both of them.

Induced sub-graph :  is obtained  by deleting a set of vertices only

Now , As we know that It's K(3,3) complete bi-partite graph

Total number of vertices = 6 

So , In each and every  vertices out 6 vertices we have a 2 choice 1) Either we deleted a vertex  2) Not deleted a vertex

therefore , total number of possible vertex induced sub-graphs = 2⁶

^{Now ,} edge induced sub-graph  is obtained  by deleting a set of edges only

Total number of Edges in complete Bi-partite graph = 3 x 3 = 9

So , In each and every  edges out 9 edges we have a 2 choice 1) Either we deleted a edges   2) Not deleted a edges

therefore, total number of possible edge induced sub-graphs = 2⁹

now , they asked , 

X : Y = 2⁶ : 2⁹ = 1:2³

therefore , X+Y = 1 + 2³ = 9 ans

 

 

 

Comments

@magma

In general , Normal Sub-graph is obtain by either you delete vertices or you delete Edges or both of them.

then how many such subgraphs possible in a given bi-partite graphk(3,3).

is it 2^6+2^9+4^15??

---

didn't understand what are you trying to say ?

---

how many  normal subgraphs possible in a given bi-partite graphk(3,3).?