Тетрадка.бгЧисла на Рамзи.

Графът е наредена двойка G=(V, E), където V е крайно множество, а E е съвкупност от 2-елементни подмножества на V. Елементите на V са върховете на графа, а елементите на E са ребрата на графа. Ако графът G´=(V´, E´) е съставен от върхове и ребра на графа G=(V, E), казваме че е G´ подграф на G. Ако два върха на подграфа G´ са съединени с ребро на G´ тогава и само тогава когато са съединени с ребро на G, казваме че G´ е породен подграф G. Два графа G´и G´´ са изоморфни тогава, когато съществува еднозначно-обратимо съответствие между V´ и V´´, при което два върха на V´ са съединени с ребро в G´ точно тогава, когато съответните им върхове са съседни с ребро в G´´. Ако всеки два върха са на един n-върхов граф са съединени с ребро, наричаме го пълен и го бележим с Кn. Нека Г е подграф на Kn, т.е. Г имам не повече от n върха. С К˜n ще означаваме подграфа на Кn, който се получава, като отстраним от Кn ребрата на Г. Следователно Кn˜ има върховете на Кn, а негови ребра са всички ребра на Кn, които не са ребра на подграфа Г. В частност, ако Г има едно ребро, графа Кn˜ ще означаваме с Кn¹. С други думи Кn¹, е подграфът на Кn, който се получава след отстраняване на едно ребро от К