# Draw a simple graph where its vertices can be divided into 2 sets where every edge joins a vertex in one set to a vertex in the other

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?

• See answer here: en.wikipedia.org/wiki/Three_utilities_problem Jan 13, 2019 at 16:00
• Is a planar requirement missing? Jan 13, 2019 at 16:04
• @ParclyTaxel no, this is the entire question given Jan 13, 2019 at 16:05
• @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? Jan 13, 2019 at 16:06
• @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." Jan 13, 2019 at 16:07

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):

• 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" Jan 13, 2019 at 16:39
• 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? Jan 13, 2019 at 16:40
• @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. Jan 13, 2019 at 16:43
• oh, i see. thank you for the clarification! 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 :

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$$