The question is:

Draw a simple graph with the following properties or explain why they do not exist. The graph has 6 vertices and 8 edges and its vertices can be divided into two sets in such a way that every edge joins a vertex in one set to a vertex in the other.

I don't understand this question but I tried doing this. Since every vertex needs to join every other vertex (for example, in the scenario with two sets where 1 set has 1 vertex and the other has 5 vertices), does this mean that for this graph to exist, there has to be n(n-1)/2 edges?

  • $\begingroup$ See answer here: en.wikipedia.org/wiki/Three_utilities_problem $\endgroup$ Jan 13, 2019 at 16:00
  • $\begingroup$ Is a planar requirement missing? $\endgroup$ Jan 13, 2019 at 16:04
  • $\begingroup$ @ParclyTaxel no, this is the entire question given $\endgroup$
    – llamaro25
    Jan 13, 2019 at 16:05
  • $\begingroup$ @DavidG.Stork in the article, the cottages are not connected to each other. in order to answer my question, i should consider the scenario where the cottages and the utilities are connected to each other right? $\endgroup$
    – llamaro25
    Jan 13, 2019 at 16:06
  • $\begingroup$ @meromero25: No. Re-read your question as stated: "in such a way that every edge joins a vertex in one set to a vertex in the other." $\endgroup$ Jan 13, 2019 at 16:07

2 Answers 2


Suppose our two vertex sets have $m$ and $n$ vertices respectively; if every edge links one vertex type to another, there can be at most $mn$ edges, when every pair of different-type vertices is connected by an edge.

In this question, $m+n=6$, so $(m,n)$ can be $(1,5),(2,4),(3,3)$, up to reversal of variables. These vertex sets allow for 5, 8 and 9 edges respectively. We reject $(m,n)=(1,5)$ as we need 8 edges. The other two choices lead to the two distinct solutions to the problem (the two vertex sets are marked with white and black circles):

  • $\begingroup$ thanks! but we should reject (3,3) as well right since it requires at least 9 edges to fulfil the statement "every edge joins a vertex in one set to a vertex in the other" $\endgroup$
    – llamaro25
    Jan 13, 2019 at 16:39
  • $\begingroup$ also, for the (1,5) and (5,1) sets, can i draw it in such a way where the set with the 5 nodes have edges that join each other too? $\endgroup$
    – llamaro25
    Jan 13, 2019 at 16:40
  • $\begingroup$ @meromero25 (1) we cannot reject $(3,3)$. There are merely more slots available for edges than we require edges. (2) no, since the edges between the set of five do not fit the problem statement. $\endgroup$ Jan 13, 2019 at 16:43
  • $\begingroup$ oh, i see. thank you for the clarification! $\endgroup$
    – llamaro25
    Jan 13, 2019 at 16:44

Without planarity requirement, the problem is only asking to have a bipartite graph : you need to be able to split the vertices in two "stable sets", i.e. two sets of vertices with no edges between vertices of the same set. As per wikipedia

a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets $U$ and $V$ such that every edge connects a vertex in $U$ to one in $V$

For example :

enter image description here

The easiest exemple fitting the question would be $K_{2,4}$, the bipartite complete graph on 6 vertices, split in two groups. $U$ has size 4, $V$ has size $2$, and all elements of $U$ are linked to all elements of $V$

enter image description here


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .