It is known that there are exactly two edge colourings with 3 colours on Ki5 that avoid monochromatic triangles,which can be constructed avertexfrom the untwisted and twisted cooringo It is also known that there are exactly 115 edge colour colours on Ki that avoid monochromatic triangles.provided that we Extensions of the theorem Clebsch graph The theorem can also be extended to hypergraphs.An m-hypergraph is a graph who in a normal graph ar edge isa set of 2 verices.The l statement of Ramsey's theorem for hypergraphs is that for any integersm and c,and any integers n,...,nc there is an integer R(n,...ncic,m)such that if the hyperedges of a complete m-hypergraph of order R(n,...,nc:c,m)are coloured with c different colours,then for some i between 1 and c,the hypergraph must contain a complete sub-m-hypergraph of order n;whose hyperedges are all colour i This theorer n is usually proved by induction on m,the hyper-ness'of the graph.The base case for the proof is m=2.which is exactly the theorem above. Infinite Ramsey theorem commonl called Ramsey's th ontext finit often ore As int d by tatio area are usually phrased in set-theoretic temminology. Theorem let x he s nd colour the el ents of x(n)(the subsets of X of size in c differ The e exists some infinite subset M of x subsets of M all have the same colour. such that the size n Proof:The proof is by induction on n,the size of the subsets.For n=1,the statement is equivalent to saying that if you split an infinite set into a finite number of sets.then one of them is infinite.This is evident Assuming the theorem is true for n sr,we prove it for n =r+1.Given a c-colouring of the (r+1)-element subsets of X,let ao be an element of X and let Y=X\{ao).We then induce a c-colouring of the r-element subsets of Y.by just adding ao to each r-element subset (to get an (r+1)-element subset of x.By the induction hypothesis,there xists an infinite subset Y of Y such that ev ry r-element subset of Y is coloured the sam e colour in the induced colouring.Thus ther e is ar element o and an infinite subset h that all the (r+1)-element subsets of X consisting of ao and r elements of Y have the same colour.By the same argument,there is an element a in Y and an infinite subset Y2 of Y with the same properties.Inductively,we obtain a sequence ao.a2 ..such that the colour of each (r+1)-element subset (a 1ai2 with i(1)<i(2)<<i(r+1 )dep nds only on the value of i(1).Furtl are infinite of i(n) such that this olour will be the e Take thes e ain)'s to ge states that every infinite graph containsClebsch graph It is known that there are exactly two edge colourings with 3 colours on K15 that avoid monochromatic triangles, which can be constructed by deleting any vertex from the untwisted and twisted colourings on K16 , respectively. It is also known that there are exactly 115 edge colourings with 3 colours on K14 that avoid monochromatic triangles, provided that we consider edge colourings that differ by a permutation of the colours as being the same. The theorem can also be extended to hypergraphs. An m-hypergraph is a graph whose "edges" are sets of m vertices – in a normal graph an edge is a set of 2 vertices. The full statement of Ramsey's theorem for hypergraphs is that for any integers m and c, and any integers n1 , …, nc , there is an integer R(n1 , …, nc ;c, m) such that if the hyperedges of a complete m-hypergraph of order R(n1 , …, nc ;c, m) are coloured with c different colours, then for some i between 1 and c, the hypergraph must contain a complete sub-m-hypergraph of order ni whose hyperedges are all colour i. This theorem is usually proved by induction on m, the 'hyper-ness' of the graph. The base case for the proof is m = 2, which is exactly the theorem above. A further result, also commonly called Ramsey's theorem, applies to infinite graphs. In a context where finite graphs are also being discussed it is often called the "Infinite Ramsey theorem". As intuition provided by the pictorial representation of a graph is diminished when moving from finite to infinite graphs, theorems in this area are usually phrased in set-theoretic terminology. [14] Theorem. Let X be some infinite set and colour the elements of X (n) (the subsets of X of size n) in c different colours. Then there exists some infinite subset M of X such that the size n subsets of M all have the same colour. Proof: The proof is by induction on n, the size of the subsets. For n = 1, the statement is equivalent to saying that if you split an infinite set into a finite number of sets, then one of them is infinite. This is evident. Assuming the theorem is true for n ≤ r, we prove it for n = r + 1. Given a c-colouring of the (r + 1)-element subsets of X, let a0 be an element of X and let Y = X \ {a0}. We then induce a c-colouring of the r-element subsets of Y, by just adding a0 to each r-element subset (to get an (r + 1)-element subset of X). By the induction hypothesis, there exists an infinite subset Y1 of Y such that every r-element subset of Y1 is coloured the same colour in the induced colouring. Thus there is an element a0 and an infinite subset Y1 such that all the (r + 1)-element subsets of X consisting of a0 and r elements of Y1 have the same colour. By the same argument, there is an element a1 in Y1 and an infinite subset Y2 of Y1 with the same properties. Inductively, we obtain a sequence {a0 , a1 , a2 , …} such that the colour of each (r + 1)-element subset (ai(1) , ai(2) , …, ai(r + 1) ) with i(1) < i(2) < ... < i(r + 1) depends only on the value of i(1). Further, there are infinitely many values of i(n) such that this colour will be the same. Take these ai(n) 's to get the desired monochromatic set. A stronger but unbalanced infinite form of Ramsey's theorem for graphs, the Erdős–Dushnik–Miller theorem, states that every infinite graph contains either a countably infinite independent set, or an infinite clique of the same cardinality as the original graph.[15] Extensions of the theorem Infinite Ramsey theorem