You are Here: Home >< Maths

# Graph Theory - Completeness and Diameter

1. Let G = (V,E) a complete graph. Then diam(G) = max d(u,v) for u,v elements of V the diameter of G (the largest distance between two vertices in G).
Let G=(V,E) a graph with |V|=n.

Prove that if d(v)>= (1/2)(n-1) for every v of V in G then diam(G)=<2.

I was fiddling around with n=0,1,2 etc..

If n=0 then we have an empty graph, so diam(G)=0.
For n=1,2,3…

N=1 then v=u so d(u,u)=0=diam(G)

For n=2 there are only two options d(u,v) or d(v,u) which are both equal to 1. So them diam(G)=2.

For n=3 then d(v)>= 1, so each vertex has at least one edge connected to it. Then you can construct a path v0,e1,v1,e2,v2 s.t. d(v0,v2)=2.

I need to construct a formal proof though..
2. Not that I've ever done graph theory, but:

Pick an arbitrary vertex A.
Call A1 the vertices distance 1 from A.
Pick an arbitrary vertex B not in A or A1.
Call B1 the vertices distance 1 from B.

Use a counting argument to show A1 and B1 must have non trivial intersection.

## Register

Thanks for posting! You just need to create an account in order to submit the post
1. this can't be left blank
2. this can't be left blank
3. this can't be left blank

6 characters or longer with both numbers and letters is safer

4. this can't be left empty
1. Oops, you need to agree to our Ts&Cs to register

Updated: May 30, 2012
TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Today on TSR

### A-level exams coming up?

Find everything you need here.

Poll
Useful resources

### Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams