# Undirected graph G that has 12 vertices, 66 edges and 3 connected components?

Why would it be impossible to draw an undirected graph G that has 12 vertices, with 3 connected components if G had 66 edges?

• What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. – Raphael Jun 12 '15 at 11:45

Hint. How many edges does the complete graph on 12 vertices have?

• I am not sure about this but the complete question goes like this. (Draw a simple undirected graph G that has 12 vertices, 18 edges, and 3 connected components. Why would it be impossible to draw G with 3 connected components if G had 66 edges?) – amulamul Jun 11 '15 at 23:44

Consider the following problem:

What is the possible maximum number of edges in $G$, which has 12 vertices and consists of 3 components (I assume that loops and multiple edges are not allowed)?

Let $n_1, n_2, n_3$ be the numbers of vertices in the three separated components. Then you are lookin for

$$\max \frac{n_1(n_1 - 1)}{2} + \frac{n_2 (n_2 - 1)}{2} + \frac{n_3 (n_3 - 1)}{2}$$ $$\text{subject to } n_1 + n_2 + n_3 = 12$$

An optimal (intuitive) solution is $n_1 = n_2 = 1, n_3 = 10$ and the maximum value is 45.