# Maximum Possible Diameter of an Undirected Graph Given Number of Edges and Nodes

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.

• sorry, I'm not familiar with the conventions of such questions. 1) do you mean that are excluded graphs constituted for example of 2 disconnected complete sub graphs ( giving an infinite distance ) ? 2) are you focused on the proof or on the result ? – user354674 Oct 2 '16 at 23:06
• 1. The graph must be connected. 2. I want a result, but I need a proof to verify it. – AlgorithmsX Oct 2 '16 at 23:16

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

• Starting from the same intuition than @heptagon in August, I find a similar result but at the opposite I have no doubt that this solution is valid for any values of $n$ and $v$. Then anteriority credit to Heptagon which is confirmed by this answer – user354674 Oct 3 '16 at 3:14
• This looks pretty good, but you might need to clean it up a bit. You have phrases like "$v$ vertices and $n$ nodes" and you don't mention edges. I am pretty sure that vertices and nodes are the same thing. I will also wait until the end of the week to award the bounty to see if anyone else can provide a better answer. – AlgorithmsX Oct 3 '16 at 3:28
• @AlgorithmsX : yes, I used the word "vertice" for "edge" ! I use sometimes a translator but not this time. I'll change the word now – user354674 Oct 3 '16 at 3:30
• Also, are you adding nodes and edges? The number of nodes and number of edges should be parameters in some function or algorithm that predicts the maximum possible diameter. – AlgorithmsX Oct 3 '16 at 3:33
• @AlgorithmsX You have them. I let you read the answer and test the javascript in scratchpad. If you see another big error of translation ( you may because you know well the question ), please let me know ... Note that as a puzzle fan, I always wait for better answers than the mines, it's better to learn that to be the best in a desert :) – user354674 Oct 3 '16 at 3:38

This is not a complete answer but rather an observation which leads to good results in some special cases. An interesting family of graphs to consider is the following. Take a complete graph $K_k$ and draw a simple path od length $v-k$ from one of its vertices. The thing you obtain has $v$ vertices, $v-(k^2-3k)/2$ edges, and diameter $v-k+1$. (The diameter is attained at a furthest point on the path and any vertex in $K_k$ that is not on the path.) A straightforward computation shows that you can get a graph with diameter $$V-\left\lceil\sqrt{2E-2V+\frac94}+\frac12\right\rceil,$$ $V$ vertices, and $E$ edges. Note that this bound is asymptotically best possible when there are not too many edges, that is, when $E=o(V^2)$, because then you get a graph with diameter $V+o(V)$. My bound is not supposed to be good for large $E$ though.

• I added a bounty to this question. – AlgorithmsX Oct 2 '16 at 22:01
• interesting intuitive answer ... I found it too but it is possible to elaborate around. I don't understand your final note ... – user354674 Oct 2 '16 at 23:49