Consider the graph G which describes the familiarity between the tourists. Clearly G is not bipartie, so G contains an odd cycle, so we choose the odd cycle C with smallest length.Since G is traingle-free l>=5, where l denotes the length of C. We assume that C= A(1)...A(l). We shall prove that if there exist a vertex B which is not in C and is adjacant to at least two vertex A(i) and A(j) of C then i and j will differ by 1 ( the index are written mod l), inparticular each vertex B of G will be adjacant to at most 2 vertex of C. Proof:Let u and v be the length of the two path which is seperated from C by removing A(i) and A(j), call those paths C(u) and C(v). Clearly u+v+2=l, so at least one of them, say u is even. Now consider the odd cycle BA(i)C(u)A(j), its length is u+3, which is odd, so u+3>= l=u+v+2, so v<=1 and thus v=1 ( since if v=0 G will have a triangle), so we are done. Now let S(i) be the number of adjacant vertices of A(i) ( for i=1,2,...l). Using the above fact, we have counted each vertex of G at most 2 times in the sum S(1)+...+S(l), thus S(1)+...+S(l)<=2n so there exist a i such that S(i)<=2n/l<=2n/5 and we are done.

Is it well-known that a non-bipartite graph contains an odd cycle? How do you prove it?

kueh wrote: Is it well-known that a non-bipartite graph contains an odd cycle? How do you prove it? It is well known, it's due to Konig in 1936, and a search reveals a proof: http://www.mathlinks.ro/Forum/viewtopic.php?t=15325 Conclusion: don't be afraid (or lazy) to use the search function

lhvietbao wrote: We shall prove that if there exist a vertex B which is not in C and is adjacant to at least two vertex A(i) and A(j) of C then i and j will differ by 1... I don't understand. There is no 3-cycles!?

Number1 wrote: I don't understand. There is no 3-cycles!? Because it was mentioned that there are no triangles in the graph. Btw, it's a very tough problem and I was quite happy with myself that I scored 3 points on it (out of 7)

I have the same dilemma as Number1 had or still have. Can you explain it loser more clearly ??

Valentin Vornicu wrote: Among every 3 of them there are 2 which are not familiar. Hence there are no triangles (3-cycles)... IS it clear now?

Yes http://www.mathlinks.ro/Forum/viewtopic.php?highlight=graph&t=68954

I still don't understand this Ihvetbao's solution. I do understand that there is no triangles. I do not understand have can then somebody (Ihvetbao) prove that there are triangles.

i guess one might add that with a point in the graph is assigned to a specific person if two persons are familiar then we trace the line with its respective points if theyre not we dont trace the line. it says that out of any three people 2 of them are not familiar hence if we have a triangle then we have three people that know each other wich is a contradiction i guess for inexperienced solvers this analogy (using graphs) is not well known now do you understand the problem? by the way its very nice!!!

Sorry for reviving an old thread, but I think I have an alternate solution (assuming this works, please point out any flaws):

The problem is equivalent to: A graph $G$ consists of $n$ vertices. Among any three vertices, there are $2$ of them that do not share an edge. Finally, $G$ is not bipartite. Prove there is a vertice with degree at most $2n/5$ Solution: Since $G$ is not bipartite, it must contain an odd cycle that is not a triangle. Consider the smallest odd cycle $S =$ {$v_1, v_2,v_3,...,v_{2k+1}, v_1$}. Note that $v_i$ may only be adjacent to $v_{i-1}$ and $v_{i+1}$ and for every vertex in $G$ \ $S$, only 2 vertices in $S$ may be adjacent to it. Otherwise, this would contradict the minimality of the length of cycle $S$. The smallest possible length for $S$ is 5 and there must exist a vertex in $S$ that has degree at most $2(n-5)/5 +2 = 2n/5$, as desired.

1) It's not bipartite graph, so there has to be odd cycle which length is greater than 3 2) Now we consider the shortest odd-length cycle $v_{1},v_{2},\cdots\,v_{2k+1}$.$(k\geq2)$ there is no edge between $v_{i}$ due to minimality condition of length 3) If every vertex has degree greater than $\frac{2n}{5}$, each vertex $v_{i}$ has some edges to vertex $x_{i}$ out of the cycle. ($ i=1,2,\cdots\,n-2k-1$) Let $G_{i}$ be the set of $x_{i}$ connected to $v_{i}$, it holds $|G_{i}|=\left\lfloor\frac{2n}{5}\right\rfloor-1$. 4) If any vertex $x_{i}$ connects $v_{j}$ more than 3, we can find contradiction easily. (More shorter cycle is found in this cycle) 5) there are at least $E=(2k+1)(\left\lfloor\frac{2n}{5}\right\rfloor-1)$ edges between $x_{i}$ and $v_{j}$. As we confirmed above, $\frac{E}{n-2k-1}\leq2$ leads to conclusion that $k<2$ by some calculation which violates length condition. So we're done.