Graph Theory - Completeness and Diameter
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..
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..
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.
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.
(edited 11 years ago)
Quick Reply
Related discussions
- A levwl biology unit 3 lung disease data
- Physics A-Level (Modelling Physics OCR Spec query)
- Edexcel A-level Biology B Paper 3 (9BI0 03) - 21st June 2023 [Exam Chat]
- A level Maths help
- Edexcel A Level Physics Paper 3: 9PH0 03 - 15th June 2023 [Exam Chat]
- ib math ai or aa
- IBDP Math AI HL IA
- AQA A-level Physics Paper 3 (7408/3) - 15th June 2023 [Exam Chat]
- gcse MCQ physics
- Maths interview prep help
- A Level Physics AQA
- Physics Magnetic fields
- Essential GCSE Physics 44.4
- Trigonometric Modelling
- Bought a Rabbit but doesn’t fit, help?
- idea silver award worker 2
- OCR A A-level Physics Unified Physics (H556/03) - 15th June 2023 [Exam Chat]
- What Maths topics are you looking forward to studying?
- Circles and triangles
- A Level Computer Science CIE
Latest
Trending
Last reply 2 days ago
Did Cambridge maths students find maths and further maths a level very easy?Last reply 2 weeks ago
Edexcel A Level Mathematics Paper 2 unofficial mark scheme correct me if wrongMaths
71
Trending
Last reply 2 days ago
Did Cambridge maths students find maths and further maths a level very easy?Last reply 2 weeks ago
Edexcel A Level Mathematics Paper 2 unofficial mark scheme correct me if wrongMaths
71
