Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

Yes, this is correct.

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.