I want to prove the next theorem:(adsbygoogle = window.adsbygoogle || []).push({});

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.

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Graph thoery question (Bondy's theorem).

**Physics Forums | Science Articles, Homework Help, Discussion**