40 Vertices And A Connected Graph, Minimum Number Of Edges?

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!

Solution 1:

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?

Solution 2:

[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.