<p>In general I would say the biggest lower bound is 1, as the graph</p>

<pre><code>a---b
</code></pre>

<p>has diameter 1 and has |V|/2 = O(|V|) edges.</p>

<p>The same holds for</p>

<pre><code>a---b---c
+-------+
</code></pre>

<p>and</p>

<pre><code>    +-------+
a---b---c---d
+-------+
</code></pre>

<p>which have exactly |V|, and |V|+1 = O(|V|) edges, respectively.</p>

<p><s>This works for an arbitrary number of graphs, as long as you fix the number of nodes.</s></p>

<p>If you restrict the number of edges not to O(|V|) but to |V|, you get a biggest lower bound of 2 for graphs of at least 4 nodes.</p>

<p><strong>EDIT</strong></p>

<p>Since the first and second example have diameter 1 with $|E| \leq |V|$ (so, clearly $|E| \in O(|V|)$) the statement that <strong>each</strong> such graph has at least diameter 2 does not hold.</p>

CC BY-SA 2.5
2010-10-29T22:16:14.970Z
What's the distance between vertex a and d in your last example? How would you do it for 5 nodes?
Michael
CC BY-SA 2.5
2010-10-29T23:39:01.810Z
If someone says “the diameter of a graph with O(|V|) edges cannot be 1,” I think that a usual interpretation is that there does not exist an infinite sequence of graphs G_1, G_2, … and a constant c>0 such that the number of vertices tends to ∞, |E(G_i)|≤c|V(G_i)|, and the diameter of every G_i is equal to 1.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-30T00:00:59.890Z
No, this is not an asymptotic statement. It says "for **every** graph with the property X the statement Y holds". This is a fundamentally different statement than "for every input the algorithms runs in O(Z(n))", where there may be a finite number of inputs where c*Z(n) does not hold. I'll edit my answer to stress this point.
bitmask
CC BY-SA 2.5
2010-10-30T00:36:04.680Z
Your last comment has two different issues.  (1) The statement “the diameter of a graph with O(|V|) edges cannot be 1” is an asymptotic statement, even if it does not look so to you.  You have interpreted the statement as something like “if a graph G satisfies |E(G)|≤c|V(G)| for some c>0, then the diameter of G cannot be 1” and disproved it, but this interpretation is simply nonsense.  (2) In my last comment, I did not say that |E(G_i)|≤c|V(G_i)| could be violated for finitely many values of i.  Therefore, your objection has nothing to do with my last comment.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-30T00:47:21.517Z
By the way, I admit that the statement “the diameter of a graph with O(|V|) edges cannot be 1” is a little sloppy.  But I think that people use statements like this in the real world, and it should be understood as a statement about infinitely many graphs.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-29T21:27:51.917Z
2010-10-30T00:03:55.567Z
2010-10-30T00:03:55.567Z
bitmask
<p>A line graph has O(V) edges and diameter V-1. A star graph also has O(V) edges and diameter 2. So it seems that the constraint that a graph has O(V) edges places almost no restriction at all on what the diameter can be. </p>

<p>Of course, 2 is the minimum, since only a complete graph has diameter 1. </p>

CC BY-SA 2.5
2010-10-12T16:43:39.883Z
arggh. stupid me. of course.
Suresh Venkat
CC BY-SA 2.5
2010-10-12T23:49:29.943Z
line graph -> path graph?
gphilip
CC BY-SA 2.5
2010-10-12T16:34:38.173Z
2010-10-12T16:41:57.857Z
2010-10-12T16:41:57.857Z
Aaron Roth
<p>What's the minimum diameter of a connected undirected graph with |V| vertices and O(|V|) edges?</p>

CC BY-SA 3.0
2013-04-30T11:30:58.453Z
This is CS.Stackexchange.com level question, not CSTheory level. is less than undergrad student exercise.
Saeed
CC BY-SA 3.0
2013-05-01T02:58:56.690Z
See also the [degree diameter problem](http://en.wikipedia.org/wiki/Degree_diameter_problem) and the [Moore bound](http://en.wikipedia.org/wiki/Moore_graph).
Austin Buchanan
CC BY-SA 2.5
2010-10-12T15:00:16.807Z
I don't understand your question: you have supplied the upper bound you seem to be asking for?
András Salamon
CC BY-SA 2.5
2010-10-12T15:01:05.793Z
I'm not sure I understand. You won't have a better upper bound than $O(V)$.  The "worst case" is a clique with a path coming out of it.  If the graph has a linear number of edges, the diameter can also be linear...
Lev Reyzin
CC BY-SA 2.5
2010-10-12T15:37:27.033Z
(1) I would say that the diameter can be ∞.  (The diameter of a graph is often defined to be ∞ if it is not connected.)  (2) Did you mean to ask for a _lower_ bound of the diameter?
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-12T16:14:10.707Z
Tsuyoshi Ito: I was thinking of connected graphs.
Alexandru
CC BY-SA 2.5
2010-10-12T16:15:44.733Z
@Andras: I only gave an example for trees. A complete graph has diameter 1 (but O(|V|^2) edges). I will try to rephrase the question.
Alexandru
CC BY-SA 2.5
2010-10-12T16:20:15.543Z
the min makes much more sense.
Suresh Venkat
CC BY-SA 2.5
2010-10-12T16:21:41.750Z
It's not clear what you want to minimize. Do you want (a) an upper bound that holds for all $O(|V|)$-edge graphs, or do you want (b) a family of graphs with $O(|V|)$ edges and minimum diameter? Note that Lev's comment is an answer for (a). Or do you want a hard upper bound on (a), with no big-O's, but rather a dependence on the constant $c$ for a $c |V|$-edge graph?
Ryan Williams
CC BY-SA 2.5
2010-10-12T16:45:01.613Z
I think he wanted (b), but Aaron's answer takes care of that. I wonder if the trick is to require the graph to be regular, to make the problem more interesting.
Suresh Venkat
CC BY-SA 2.5
2010-10-12T18:14:12.327Z
If all degrees are at most $c$ then there's a lower-bound on diameter of $\Omega(\log_{c} |V|)$ because at most $c^d$ vertices are within distance $d$ of any single vertex. I presume that Aaron's example can be modified to show that this is tight.
Warren Schudy
CC BY-SA 2.5
2010-10-12T18:51:20.127Z
Warren's analysis is tight as shown by balanced c-ary trees.
Aaron Roth
<graph-theory><co.combinatorics>
Diameter of a graph with O(|V|) edges
Alexandru
# Diameter of a graph with O(|V|) edges

(Asked by: username_0 on 2010-10-12)

What's the minimum diameter of a connected undirected graph with |V| vertices and O(|V|) edges?

**Tags:** graph-theory, co.combinatorics
> **Comments:**
> **username_3**: I don't understand your question: you have supplied the upper bound you seem to be asking for?  
> **username_4**: I'm not sure I understand. You won't have a better upper bound than $O(V)$.  The "worst case" is a clique with a path coming out of it.  If the graph has a linear number of edges, the diameter can also be linear...  
> **username_5**: (1) I would say that the diameter can be ∞.  (The diameter of a graph is often defined to be ∞ if it is not connected.)  (2) Did you mean to ask for a _lower_ bound of the diameter?  
> **username_0**: Tsuyoshi Ito: I was thinking of connected graphs.  
> **username_0**: @Andras: I only gave an example for trees. A complete graph has diameter 1 (but O(|V|^2) edges). I will try to rephrase the question.  
> **username_6**: the min makes much more sense.  
> **username_7**: It's not clear what you want to minimize. Do you want (a) an upper bound that holds for all $O(|V|)$-edge graphs, or do you want (b) a family of graphs with $O(|V|)$ edges and minimum diameter? Note that Lev's comment is an answer for (a). Or do you want a hard upper bound on (a), with no big-O's, but rather a dependence on the constant $c$ for a $c |V|$-edge graph?  
> **username_6**: I think he wanted (b), but Aaron's answer takes care of that. I wonder if the trick is to require the graph to be regular, to make the problem more interesting.  
> **username_8**: If all degrees are at most $c$ then there's a lower-bound on diameter of $\Omega(\log_{c} |V|)$ because at most $c^d$ vertices are within distance $d$ of any single vertex. I presume that Aaron's example can be modified to show that this is tight.  
> **username_9**: Warren's analysis is tight as shown by balanced c-ary trees.  
> **username_1**: This is CS.Stackexchange.com level question, not CSTheory level. is less than undergrad student exercise.  
> **username_2**: See also the [degree diameter problem](http://en.wikipedia.org/wiki/Degree_diameter_problem) and the [Moore bound](http://en.wikipedia.org/wiki/Moore_graph).  

---

## 2 answers

### Answer by username_9 on 2010-10-12. Score: 21 | Accepted answer

A line graph has O(V) edges and diameter V-1. A star graph also has O(V) edges and diameter 2. So it seems that the constraint that a graph has O(V) edges places almost no restriction at all on what the diameter can be.

Of course, 2 is the minimum, since only a complete graph has diameter 1.

> **Comments:**
> **username_6**: arggh. stupid me. of course.  
> **username_12**: line graph -> path graph?  

---

### Answer by username_10 on 2010-10-29. Score: -1

In general I would say the biggest lower bound is 1, as the graph
a---b

has diameter 1 and has |V|/2 = O(|V|) edges.
The same holds for
a---b---c
+-------+

and
    +-------+
a---b---c---d
+-------+

which have exactly |V|, and |V|+1 = O(|V|) edges, respectively.
This works for an arbitrary number of graphs, as long as you fix the number of nodes.
If you restrict the number of edges not to O(|V|) but to |V|, you get a biggest lower bound of 2 for graphs of at least 4 nodes.
EDIT
Since the first and second example have diameter 1 with $|E| \leq |V|$ (so, clearly $|E| \in O(|V|)$) the statement that each such graph has at least diameter 2 does not hold.

> **Comments:**
> **username_11**: What's the distance between vertex a and d in your last example? How would you do it for 5 nodes?  
> **username_5**: If someone says “the diameter of a graph with O(|V|) edges cannot be 1,” I think that a usual interpretation is that there does not exist an infinite sequence of graphs G_1, G_2, … and a constant c>0 such that the number of vertices tends to ∞, |E(G_i)|≤c|V(G_i)|, and the diameter of every G_i is equal to 1.  
> **username_10**: No, this is not an asymptotic statement. It says "for **every** graph with the property X the statement Y holds". This is a fundamentally different statement than "for every input the algorithms runs in O(Z(n))", where there may be a finite number of inputs where c*Z(n) does not hold. I'll edit my answer to stress this point.  
> **username_5**: Your last comment has two different issues.  (1) The statement “the diameter of a graph with O(|V|) edges cannot be 1” is an asymptotic statement, even if it does not look so to you.  You have interpreted the statement as something like “if a graph G satisfies |E(G)|≤c|V(G)| for some c>0, then the diameter of G cannot be 1” and disproved it, but this interpretation is simply nonsense.  (2) In my last comment, I did not say that |E(G_i)|≤c|V(G_i)| could be violated for finitely many values of i.  Therefore, your objection has nothing to do with my last comment.  
> **username_5**: By the way, I admit that the statement “the diameter of a graph with O(|V|) edges cannot be 1” is a little sloppy.  But I think that people use statements like this in the real world, and it should be understood as a statement about infinitely many graphs.  

---

