Теория графов и комбинаторика

Рко.9.1 2. "а" "с5". Связноотъ (? кепооредотввнно-следует из ус­ ловия "а". Докажем, что f = + < , индукцией по числу вершин Р • • Для р=Д; утверждение оправедошво. Пусть оно оправедливо дашр < и . Рассмотрим граф с vl вершинами ( р = п ) , для которо­ г о вылолняется условие "а". Внберен. Ч Tyl/t £ У . Для них 3{ простая fiT-liJ*) - цепъ р . Пуоть 0G - Bs^ jTopoa ребро цепи Р . Удалим это рвйро. Тогда в графе нет C'tT-t »? ) - цепей. Сле­ довательно, - а; несвязный граф, имекхдай две компоненты , и о чиолаш вершин и pedep состветотвенио С p i , <1< ) и С Рд, , I'n, ) . Очевидно, дам <?< и вьгаолняетоя условие "а". Так как Pi J Pj, < И , то индуктивному предположению Р, + "1 . Суммируя эти равенства, получим; Р ) + • . • Таким образом, ^ у. Y , что и требовалось доказать. 3 . „ S " . Докажем ацикличность графа (Р . пусть в ^ имеетоя проотой дикл Z длины и . Он содержит и разных вершин иУ) разннх ребер; вне цикла Z - (р-и) вершин. Так как граф S- стлзный, то каждая из вершин "^ие цикла соединена с некоторой' вершиной цикла марпг^том. Дли этого должно понадобиться, по крайней мере, р-и ребер. Следовательно, У1 +; р -и^ г р , Это неравенство противоречит условии . Ацикличность & ; доказана. 4 . " ^ " •s^ " ^ - дерево". Ацикличноот &• дана. Докажем овязиооть. Пуоть <? £ , с - ; , и - комдонентн графа G- с числами вершин и ребер ё-i - ациклический граф, т . к . ациклическим является Q ' . Таким образом, графы'^с, ll=^7Й яашшгоя деревьями. Тогда по уоловию "б" Iri+'i ^ ,•Просуммируем все эти равенства: ^ Рг - ^ ^ г +И • Отовда р . Но до уоловв» "в''рг^+f. , следоватально, чис­ ло коадояент графа б- №«•(' , т . е . граф (? овязный, • ' - 54