Graph thoery question (Bondy's theorem).

[MathematicalPhysicist]

I want to prove the next theorem:
Let A1,...,An be n distinct subsets of the set N:={1,2,...,n}, then there exists x in N s.t thr sets Ai-{x}, 1<=i<=n are all distinct.

Now next I was given the hint:
Let G be a graph with Ai as its vertices, and an edge with "colour" x between Ai and Aj, such that the symmetric difference of Ai and Aj is {x}, i.e x is in Ai or Aj but not in both of them.
Now it states that I need to show that one can delete edges from G in such a way that no polygons are left and the number of different colours remains the same.

Now let me know if I got it right:

1. If I show this, then if there isn't a polygon and the number of colours remains the same it means that we still have n vertices, but these vertices are composed of the sets Ai-{x}, cause if not then every vertex would be connected to another one by the coloured edge x, which means x is in every Ai, which is impossible.
The reason why the number of colours stays the same is because we delete from every set Ai, the point x from N, and because the sets Ai are distinct, the number of colours stays the same even after we remove the edges which construct a polygon.
A polygon here means that there are k,m s.t for every i in N: x isn't in Ak and isn't in Am, if we delete x from Ai, then we deleted the polygon, but then again x is in some Aj (Ap), where Aj (Ap) is adjacent to Am (Ak), for example, which means we constructed another (two) edge(s) between Aj (Ap) and Ai, now delete x from Aj (Ap), now if we continue this process, eventaully we'll get a star shaped graph, where all the edges are centred on one vertex, s.t the number of colours remains the same, but there's no polygon , which means the sets Ai-{x} are distinct.

 

[mXSCNT]

It's difficult for me to read that because I have no idea what a polygon is. (Do you mean a cycle?) The second part of the hint does not make sense to me. The first part is good though.

The important thing is that if two sets are connected by an edge of color x, that means that x can't be the color that satisfies the theorem, since if you removed x from both sets then they would be the same. In fact, x satisfies the condition of the theorem if and only if there are no edges of color x. So what we need to prove is that there is at least one color that there are no edges of.

Suppose that this is not true, i.e. that we have edges of all n colors in the graph. Pick a subset of these edges such that each color is represented exactly once in the subset. Since the largest acyclic graph on n vertices has n-1 edges, the n edges in our subset must form at least one cycle C, with nodes C_1, C_2, ..., C_k in order. C_1 and C_2 must differ from each other by a color x (since they are adjacent). Without loss of generality, suppose that C_2 is the node that has x as an element, and C_1 is the node without it. We know that all of the edges in the cycle have different colors. Therefore the edge C_2 C_3 is not color x, so C_3 must also have x as an element. Similarly the edge C_3 C_4 is not color x, so C_4 must also have x as an element. And so on by induction around the cycle, down to C_k C_1, which proves that C_1 must have x as an element, which contradicts our assumption.

Therefore by contradiction, there is some x in N that is not the color of any edge, so we can remove x from each A_i and all the A_i will still be distinct.

 

[MathematicalPhysicist]

A polygon, is the same as a closed cycle.

Thanks for the help.
I must admit, that the colour business was funny for me too, with the second part of the hint.