10
$\begingroup$
  1. There's a connected graph with 40 vertices, what is the minimum amount of edges there could be?
  2. There's a graph with 40 vertices, what is the minimum amount of edges that guarantees a connected graph?

My thoughts for number 1: The very least, each vertex must have an edge starting from itself and connecting to another vertice, so I think the answer to this question is $40$ edges, am I right?


My thoughts for number 2: We want the biggest number of edges without connecting all of them. So we take out just 1 vertex and connect all the other vertices to its maximum number of edges, which is $\binom{39}{2}=741.$ Then we just simply connect the remaining vertex to the other 39 vertices and get $742,$ am I correct?


Could someone please confirm or correct my answer for question 1 and post a solution for number 2? Thanks in advance!

$\endgroup$
  • 4
    $\begingroup$ Hint for both questions: try doing it with a graph on a small number of vertices, like 2, or 3, or 4. There is nothing special about the number 40. $\endgroup$ – Mees de Vries Nov 7 '16 at 14:42
  • 6
    $\begingroup$ (1) I can think of a connected graph with 40 vertices but only 39 edges. $\endgroup$ – Henning Makholm Nov 7 '16 at 14:43
  • 3
    $\begingroup$ Language nitpick: One "vertex", two "vertices". (You can avoid the unusual plural by speaking about "nodes" instead). $\endgroup$ – Henning Makholm Nov 7 '16 at 15:21
  • $\begingroup$ @HenningMakholm Thanks for pointing that out! I knew there was something weird about my math language in there. $\endgroup$ – Dreamer Nov 7 '16 at 15:28
12
$\begingroup$

[Edit: for the sake of completeness I added, in the end, the proof for the right answer for 2]

You missed the right answer for 1) by 1! Imagine you order all your 40 vertices in a line and then connect each one to the next. Then you would have 39 edges and your graph would be connected. Therefore a graph with $k$ vertices needs at least $k-1$ edges to be connected...

Now to answer your second question... What is the "worst case scenario" of having edges distributed in your graph and still not having a connected graph?? Well, just imagine you leave one vertex standing there with no edges and completely connect all $k-1$ vertices left! How many edges does that make? Is that enough?

One can prove that that is the maximum number of edges a graph with $k$ vertices can have and still not be connected. Why is that?

(if after thinking a bit about this you do not convince yourself of that fact and/or you can't prove it, I can write the proof for you. But you have to try hard enough.)

Proof:

Let $n $ be the number of vertices of a graph. We show that ${n-1}\choose{2} $$+1$ is the minimum number of edges the graph must have in order for us to be sure that the graph is connected. For that we first show that if the graph has ${n-1}\choose{2}$ edges then it need not be connected.

That statment holds trivially: pick one vertex and consider the $n-1$ vertices left. We can connect all of them with ${n-1}\choose{2} $ edges. Because there was a vertex that had been set aside, that vertex has no incident edges and therefore is isolated from the rest of the graoh i.e. the graph is not connected.

Secondly we show that there is no way to distribute ${n-1}\choose{2} $$+1$ edges among $n $ vertices that leaves the graph disconnected. We assume there is such a distribution. Then the graph can be split into two components. One $G_1$ with $k $ vertices and the other, $G_2$, with $n-k $. Without loss of generality assume $k \le n-k $. For those two components to have as many edges as they can, they must be fully connected. That means every vertex on $G_1$ has $k-1$ edges and every vertex on $G_2$ has $n-k-1$ edges.

Now because $G_2$ has more vertices than $G_1$, we could pick a vertex from $G_1$, erase all its edges, move it to $G_2$ and connect it to every vertex there. That would be creating at least as many edges as it destroyed, so it is not decreasing the total number of edges in our graph. We can repeat this process to actually increase it. As long as there are vertices remaining in $G_1$ this leaves the graph disconnected. So the minimum number of vertices in $G_1$ is 1. But that is exactly the case above so there is one edge left to assign, and it must connect the only vertex from $G_1$ to some vertex in $G_2$ making the graph connected.

Showing that for any disconnected graph split in more than 2 components you can have a disconnected graph with more edges and only 2 components, we show that splitting $G $ into $G_1$ and $G_2$ was our best shot, but in that case we could not have done any better. So having ${n-1}\choose{2} $$+1$ edges is enough to guarantee that the graph is connected.

$\endgroup$
  • $\begingroup$ How can a graph not be connected if all the vertices are connected(which is what a graph with maximum amount of edges look like)? Wouldn't that make the question impossible? $\endgroup$ – Dreamer Nov 7 '16 at 14:59
  • $\begingroup$ @Regina you may have misunderstood me Or I didn't explain myself correctly. Just imagine the graph has $k $ vertices. Now set one of them aside, alone, with no edges. Now *completely* connect all the other $k-1$ vertices. The whole graph is not connected although you have a strongly connected component $\endgroup$ – RGS Nov 7 '16 at 15:04
  • $\begingroup$ Oh, okay. Here's my proof: We want the biggest number of edges without connecting all of them. So we take out just 1 vertice and connect all the other vertices to its maximum number of edges, which is $\binom{39}{2}=741.$ Then we just simply connect the remaining vertice to the other $39$ vertices and get $\boxed{742},$ am I correct? $\endgroup$ – Dreamer Nov 7 '16 at 15:15
  • $\begingroup$ @Regina "One vertex", not "one vertice" but otherwise, you're correct. $\endgroup$ – saulspatz Nov 7 '16 at 16:19
  • 2
    $\begingroup$ @Regina You have shown that there is a graph with 741 edges that is not connected, and a graph with 742 edges that is connected. But that does not quite prove the property you want. (I can show there is a graph with 99 edges that is not connected, and a graph with 100 edges that is connected, but 100 is not the correct answer to this question!) To prove that 742 is the right answer, you have to show that every graph with 40 vertices and 742 edges is connected. $\endgroup$ – Daniel Wagner Nov 7 '16 at 22:07
13
$\begingroup$

For (2), it seems to be more fruitful to think about what the maximum number of edged for a not connected graph is. (The number you're looking for is then one more than that).

If a graph is not connected, its vertices will split into two groups that don't connect to each other -- say, choose one vertex and let one group consist of all vertices connected to that one, and the other group be all other vertices.

Suppose the groups have size $a$ and $b$, with $a+b=40$. Then the maximal number of edges the graph can have is $\binom{a}{2}+\binom{b}{2}$, but a more useful way of writing this is $\binom{a+b}{2}-ab$, namely the complete graph minus the number of edges that would connect the two groups. Since we have $b=40-a$, we need to minimize the function $a\mapsto a(40-a)$ under the constraint that $a$ is an integer between $1$ and $39$, inclusive.

Can you complete it from here?

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