-2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Raphael Jun 12 '15 at 11:45
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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?) $\endgroup$ – amulamul Jun 11 '15 at 23:44
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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