2
$\begingroup$

A bipartite graph G contains set of people in one partition (call each node as people node) and their interests in other partition (call it as interest node). There are edges between people and their interests so two people may share same interest vice versa,but there cannot be edge within same partition (as bipartite graph says). Now, from above I'll draw a projected graph $G'(V',E')$ such that

$V' := \{ v \in V \mid v \textrm{ is a people node}\}$

$E' := \{ (u,v) \in V'^2 \mid \textrm{ $u$, $v$ share at least one interest}\}$

So conversion from $G$ to $G'$ is easy but I've $G'$ now and I want to convert it to $G$ with minimum number of interest nodes. So in order to generalize above "reverse conversion",my claim is,

Decompose $G'$ into minimum number of complete graphs such that each edge of $G'$ must be included in at least one complete graph.The number of complete graphs you get in above decomposition is the number of minimum interest nodes required.

Is it correct?

1 Answers 1

1

Yes, this is correct.

It is worth mentioning that different bipartite graphs may give the same projected graph.