AoPS - Problem

Source: 12-th Hungary-Israel Binational Mathematical Competition 2001

Tags: graph theory, combinatorics unsolved, combinatorics

N.T.TUAN

19.04.2007 08:04

Here $G_{n}$ denotes a simple undirected graph with $n$ vertices, $K_{n}$ denotes the complete graph with $n$ vertices, $K_{n,m}$ the complete bipartite graph whose components have $m$ and $n$ vertices, and $C_{n}$ a circuit with $n$ vertices. The number of edges in the graph $G_{n}$ is denoted $e(G_{n})$. (a) If $G_{n}$ does not contain $K_{2,3}$ , prove that $e(G_{n}) \leq\frac{n\sqrt{n}}{\sqrt{2}}+n$. (b) Given $n \geq 16$ distinct points $P_{1}, . . . , P_{n}$ in the plane, prove that at most $n\sqrt{n}$ of the segments $P_{i}P_{j}$ have unit length.

.We call all vertices of $G_{n}$ be : $A_{1}; A_{2};,..,; A_{n}$ with the dgree of $A_{i}$ alternately be $d_{i};,..; d_{n}$ It is well known that : $e( G_{n})= \sum_{i=1}^{n}d_{i}$ . We will prove that if $G_{n}$ does not contain a $K_{2,3}$ then : $e(G_{n}) \leq \ frac{n+n.\sqrt{8.n-7}}{4}$. It is'nt not hard to prove this ! b. We construct a graph whose verices are the n givens points and any two connected by an edge if and only if the segments they form has unit lenght Assume $G_{n}$ contains a $K_{2,3}$ then there are two points say A, B with are connected three other common points say C,D,E Hence the circle with radius 1 and centers A,B intersected in at least three points , contradiction ! Apply a we have $e(G_{n}) \leq \ frac{n+n.\sqrt{8.n-7}}{4}$. Since : $\ frac{n+n.\sqrt{8.n-7}}{4}\leq n.\sqrt{n}$ whch holds for all n>15 ->qed