|
В следующих вопросах,
G_n — простой неориентированный граф с n вершинами,
K_n — полный граф с n вершинами,
K_(n,m) — полный двудольный граф с m вершинами на одной части и n вершинами на другой части,
C_n — цикл с n вершинами.
e(G_n) — количество ребер в графе G_n.
1.Ребра K_n (n≥3) покрашены в n цветов, каждый цвет использовался по крайней мере 1 раз. Докажите, что есть треугольник, чьи стороны раскрашены в три различных цвета.
2. n≥5. Если e(G_n )≥n^2/4+2, докажите, что в G_n существует два треугольника, которые имеют ровно одну общую вершину.
3. e(G_n )≥(n√n)/2+n/4. Докажите, что G_n содержит C_4.
4. а) G_n не содержит K_2,3. Докажите, что e(G_n )≤(n√n)/√2+n.
б) Дано n≥16 различных точек P_1, P_2, …, P_n на плоскости, докажите, что не более n√n отрезков P_i P_j имеют единичную длину.
5. а) Пусть p — простое. Рассмотрим множество {(x,y)|0≤x,y≤p-1} вершин таких, что (x,y), (x^',y') соединены если xx^'+yy^'≡1 (mod p). Докажите, что граф не содержит C_4.
б) Докажите, что для бесконечно многих значений n существует граф G_n не содержащий C_4 и e(G_n )≥(n√n)/2-n.
|
09.04.2015, 23:26 