You are Here: Home >< Maths

# Graph Theory - Completeness and Diameter Watch

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.

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

### Stuck for things to do this summer?

Come and get some inspiration.

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