Let M = {a, b, c, d, e}. We form a graph G = (V, E), where the set of vertices V consists of all subsets of two elements from set M (i.e., for example {a, d} ∈ V), and there is an edge between two vertices if and only if the corresponding sets have an empty intersection. Due to symmetry, all vertices have the same degree.

a) How many vertices are there in the graph G?

b) Draw the graph G.

c) Calculate the chromatic number of the graph G.

  • $\begingroup$ An expectation on this site are that you share what you have tried or what is your motivation for asking this question. You will not get any responses if you post verbatim a question that looks like a textbook exercise or homework problem. Please edit your post. $\endgroup$ May 15 at 17:29


You must log in to answer this question.

Browse other questions tagged .