- There's a connected graph with 40 vertices, what is the minimum amount of edges there could be?
- 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!
Best Answer
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?