You are Here: Home

# Graph Theory - Completeness and Diameter

Announcements Posted on
Talking about ISA/EMPA specifics is against our guidelines - read more here 28-04-2016
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

### How to predict exam questions

No crystal ball required

Poll
Useful resources

### Maths Forum posting guidelines

Not sure where to post? Read here first

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams