[Math] Maximum Possible Diameter of an Undirected Graph Given Number of Edges and Nodes

Question

The title is pretty self explanatory. If I have $V$ nodes and $E$ edges in a connected undirected graph, is there a formula to determine an upper bound on the maximum possible diameter? The exact graph is unknown, but the number of edges and the number of vertices is. I do know that when $E=V(V-1)/2$ (complete graph), the maximum possible diameter is $1$, and when $E=V-1$ (line graph), the maximum possible diameter is $V-1$, but I have no idea about anything in between.

Answer 1

We assume that $v \geq n-1 $ and $v \leq \frac{n(n-1)}{2}$

Given $v$ edges and $n$ nodes, let's compute the minimal number of nodes $u$ needed to spend the excess of edges in a spending-hole $SH$:

We know that the saturation of $u$ nodes needs $\frac{n(n-1)}{2}$ edges and it remains $w = n-u$ edges to constitute a linear graph generator of long distances.

First, let's try to minimize $u$ and maximize $w$ in :

• $n = w + u$
• $v = w-1 + 1 + \frac{u(u-1)}{2}$

where $w-1$ is for the long distance subgraph , $\frac{u(u-1)}{2}$ for the spending-hole $SH$ and $1$ edge to join them.

• $=> u' = \frac{(3+\sqrt{(8(v-n)+9)})}{2}$
• $=> u = \lceil {u'} \rceil = \lceil {\frac{(3+\sqrt{(8(v-n)+9)})}{2} }\rceil$ ,

$ceil(u')$ because we deal with integers and $u'$ was just a computed bound.

Then we compute the remaining nodes $n-u$ , we take from the $SH$ as many edges needed to reach $n-u$ and we may compute the distance $d = n-u +1$ which must be added $1$ if the $SH$ is saturated, ie if $\frac{u(u-1)}{2}-u= v-n$ .

Numerical application :

/*
main(5,true) :
5 nodes :

for v=4 : 2 nodes will consume 1 edges from 1 ; it remains 3 nodes 3 edges,d =4

      5 : 3                    3               3 ;            2       2             3

      6 : 4                    5               6 ;            1       1             3
      7 : 4                    6               6 ;            1       1             2

      8 : 5                    8              10 ;            0       0             2
      9 : 5                    9              10 ;            0       0             2
     10 : 5                   10              10 ;            0       0             1

Note how the distance $d$ changes with the edges in excess and how it decreases by $1$ when the $SH$ is saturated. I recall that the number of edges is bounded by the question and we cannot have double edges, no edges or edges without nodes.

function main(n,all)
{
    var u , spent , spentmax , v , V = n*(n-1)/2 , res = n+" nodes :\n" , exm = -1,d , firstline = true ;

    for ( v = n-1 ; v <= V ; v ++ )
    {
        u = Math.ceil( (3+Math.sqrt(8*(v-n)+9))/2 ) ;
        spentmax = (u*(u-1)/2)  ;
        spent = (v-n+u) ;
        if(u!=exm || all )
        {
            if(u!=exm )
            {
                if( all ) res += "\n" ;
                exm = u ;               
            }

            d = 1 + n-u + ( spentmax == spent ? 0 : 1 );
            if( firstline )
                res += ( "for v="+v+" : "+u +" nodes will consume "+spent+" edges from "+spentmax+" ; it remains "+(n-u)+" nodes " + (v-spent) +
                                " edges,d ="+d+"\n" ) ;
            else
                res += ( "      "+v+" : "+u +"                    "+spent+"               "+spentmax+" ;            "+(n-u)+"       " + (v-spent) +
                                "             "+d+"\n" ) ;

            firstline = false ;
        }
    }
    return res ;
}

// scratchpad formalism to get the result by typing CTRL L at the end of the script
var z1 , z2 = main(5,false) ;     // number of nodes and true to get all the intermediate edges steps
z1=z2;

/*
main(12,false) :
12 nodes :
for v=11 : 2 nodes will consume 1 edges from 1 ; it remains 10 nodes 10 edges,d =11
      12 : 3                    3               3 ;            9       9            10
      13 : 4                    5               6 ;            8       8            10
      15 : 5                    8              10 ;            7       7             9
      18 : 6                   12              15 ;            6       6             8
      22 : 7                   17              21 ;            5       5             7
      27 : 8                   23              28 ;            4       4             6
      33 : 9                   30              36 ;            3       3             5
      40 : 10                  38              45 ;            2       2             4
      48 : 11                  47              55 ;            1       1             3
      57 : 12                  57              66 ;            0       0             2    */

Even if the proof is not fundamentally detailed, one can see that the construction is minimal, starting from a linear graph with $v = n-1$ and adding the edges in excess in a Spending hole ( or a ball of wool if one prefers ). When the latter is saturated, we "sacrify" a new node until a new saturation. When all the edges in excess have used a minimum of nodes, it remains a piece of linear graph which is joined to the $SH$ by one edge to one node.

The same question with the possibility of not connection is interesting too ... This kind of problems has a lot of applications when the algorithm may add nodes at its convienience ( Steiner tree problems family ).

ps : feel free to edit and correct obscure translations, TY