GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
76 views

Let $S$ be a set of $n$ points in the plane, the distance between any two of which is at least one. Show that there are at most $3n$ pairs of points of S at distance exactly one.

 

Can this be done with a unit circle and we can place at max. $6$ points on the perimeter and doing the same for other points as well ? i.e. we can get $6n/2 = 3n$ pairs at max. ? 
 

asked in Graph Theory by Veteran (51.5k points)   | 76 views

Please log in or register to answer this question.



Top Users Sep 2017
  1. Habibkhan

    7194 Points

  2. Warrior

    2686 Points

  3. Arjun

    2594 Points

  4. rishu_darkshadow

    2568 Points

  5. A_i_$_h

    2280 Points

  6. nikunj

    1980 Points

  7. manu00x

    1856 Points

  8. makhdoom ghaya

    1770 Points

  9. Bikram

    1744 Points

  10. SiddharthMahapatra

    1718 Points


26,164 questions
33,743 answers
79,994 comments
31,124 users