Register

Graph Theory : Bondy-Murty $1.1.20$

311 views
1 votes
1 votes

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. ? 
 

User Avatar

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

2 votes
2 votes
0 answers
1
dd asked Jul 4, 2017
446 views
Graph Degree sequence : Bondy and Murty : $1.1.16$
Let $d = (d_1,d_2,\dots, d_n)$ be a nonincreasing sequence of nonnegative integers, that is, $d_1 \geq d_2 \geq · · · \geq d_n \geq 0$. Show that: there is a loopless graph with degree sequence d if and only if $\sum_{i=1}^{n}d_i$ is even and $d_1 \leq \sum_{i=2}^{n}d_i$
Let $d = (d_1,d_2,\dots, d_n)$ be a nonincreasing sequence of nonnegative integers, that is, $d_1 \geq d_2 \geq · · · \geq d_n \geq 0$. Show that:there is a loopless g...
User Avatar
3 votes
3 votes
0 answers
4
dd asked Jul 1, 2017
381 views
Minimum No. of vertices required
Prove the following for graph $G$. When length of the shortest cycle in a graph is $k \geq 3$ and the minimum degree of the graph is $d$, then $G$ ... $k$.
Prove the following for graph $G$.When length of the shortest cycle in a graph is $k \geq 3$ and the minimum degree of the graph is $d$, then $G$ has minimum $\begin{alig...
User Avatar
Link Copied!