5.5: Планарні графіки

Доказ Наш доказ – індукція на \(m\) кількість ребер. Якщо \(m=0\) , то так як \(G\) пов’язаний, наш граф має єдину вершину, і так є одна грань. При цьому \(n−m+f=1−0+1=2\) в міру необхідності. Тепер припустимо, що ми довели формулу Ейлера для всіх графів з менш ніж m ребер і нехай \(G\) мають \(m\) ребра. Підберіть \(e\) край \(G\) . Що станеться, якщо ми сформуємо новий графік \(G′\) , видаливши e з \(G\) ? Якщо \(G′\) пов’язано, застосовується наша індуктивна гіпотеза. Скажімо, що \(G′\) має \(n′\) вершини, \(m′\) ребра та \(f′\) грані. Тоді за допомогою індукції ці числа задовольняють \(n’ – m’ + f’ = 2\) . Так як ми видалили тільки один край, \(n′=n\) і \(m′=m−1\) . Що \(e\) зробило видалення з числа осіб? У \(G′\) є нове обличчя, яке раніше було двома обличчями, розділеними на \(e\) в \(G\) . Таким чином, \(f′=f−1\) . Підставляючи їх в \(n′−m′+f′=2\) , ми маємо \(n-(m-1) + (f-1) = 2 \Longleftrightarrow n-m+f = 2\) . Таким чином, якщо \(G′\) підключено, ми зробили. Однак, якщо \(G′\) відключений, ми не можемо застосувати індуктивне припущення \(G′\) безпосередньо. На щастя, оскільки ми видалили лише одне ребро, \(G′\) має дві складові, які ми можемо розглядати як два з’єднаних графіка \(G_1′\) і \(G_2′\) . Кожен з них має менше \(m\) країв, тому ми можемо застосувати до них індуктивну гіпотезу. Для \(i=1,2\) , \(n_i′\) нехай число вершин \(G_i′, m_i′\) числа ребер від \(G_i′, and f_i′\) числа граней \(G_i′\) . Тоді за допомогою індукції ми маємо \(n_1′ – m_1′ +f_1′ = 2\) і \(n_2′ – m_2′ + f_2′ = 2\) . Додавши їх разом, ми маємо \((n_1′ + n_2′) – (m_1′ + m_2′) + (f_1′ + f_2′) = 4\) . Але зараз \(n=n_1′ + n_2’\) і \(m_1′ + m_2′ = m-1\) , таким чином рівність стає \(n – (m-1) + (f_1′ + f_2′) = 4 \Longleftrightarrow n-m + (f_1′ + f_2′) = 3\) . Єдине, що нам ще належить з’ясувати, це те \(f\) , як \(f_1′+f_2′\) відноситься до, і ми повинні сподіватися, що це дозволить нам збити 3 вниз до 2. Кожна грань \(G_1′\) і \(G_2′\) є обличчям \(G\) , так як той факт, що видалення \(e\) роз’єднує \(G\) означає, що \(e\) повинна бути частиною кордону необмеженої грані. Далі необмежений грань підраховується двічі в сумі \(f_1′+f_2′\) , так \(f=f_1′+f_2′−1\) . Це дає саме те, що нам потрібно для завершення доказу. Взята сама по собі формула Ейлера не здається такою корисною, оскільки вона вимагає підрахунку кількості граней у планарному вбудовуванні. Однак ми можемо використовувати цю формулу, щоб отримати швидкий спосіб визначити, що графік не є планарним. Розглянемо креслення без перетинів ребер графа по \(n\) вершинам і m ребрам, с \(n \geq 3\) . Розглядаємо пари \((e,F)\) , де \(e\) є ребром \(G\) і \(F\) є грань, яка має \(e\) як частину своєї межі. Скільки таких пар? Назвемо кількість пар \(p\) . Кожен край може зв’язати або одну або дві грані, так що у нас є, що \(p \leq 2m\) . Ми також можемо зв’язати, \(p\) підрахувавши кількість пар, в яких \(F\) з’являється обличчя. Кожна грань обмежена як мінімум 3 ребрами, тому вона з’являється як мінімум в 3 пари, і так \(p \geq 3f\) . Таким чином \(3f \leq 2m\) або \(f \leq 2m/3\) . Тепер, використовуючи формулу Ейлера, ми маємо \(m=n+f – 2 \leq n + \frac – 2 \Longleftrightarrow \frac \leq n-2\) . Таким чином, ми довели наступну теорему.

Теорема 5.33

Контрапозитив цієї теореми, а саме те, що \(n\) -вершинний граф з більш ніж \(3n−6\) ребрами не є площинним, зазвичай є найбільш корисним формулюванням цього результату. Наприклад, ми бачили (рис. 5.31), що \(K_4\) є площинним. А як щодо \(K_5\) ? Він має 5 вершин і \(C(5,2)=10>9=3 \cdot 5−6\) ребер, тому він не плоский, і, таким чином \(n \geq 5\) , для, \(K_n\) не плоский, так як містить \(K_5\) . Важливо зазначити, що теорема 5.33 – це не все, кінець визначення того, чи граф є планарним. Щоб переконатися в цьому, повернемося до теми малювання \(K_\) в площині. Цей граф має 6 вершин і 9 ребер, тому він проходить тест теореми 5.33. Однак, якщо ви витратите пару хвилин, намагаючись знайти спосіб малювати \(K_\) в площині без будь-яких перетинання країв, ви досить швидко почнете вірити, що це неможливо зробити – і ви б мали рацію! Щоб зрозуміти, \(K_\) чому не плоска, нам доведеться повернутися до формули Ейлера, і ми знову працюємо з парами края-грань. Бо ми бачимо \(K_\) , що кожне ребро повинно бути частиною кордону двох граней, а грані обмежені циклами. Також, оскільки графік двосторонній, непарних циклів немає. Таким чином, підраховуючи пари края-грань з точки зору краю, ми бачимо, що є \(2m=18\) пари. Якщо ми \(f_k\) дозволимо кількість граней, обмежених циклом довжини \(k\) , то \(f=f_4+f_6\) . Таким чином, підраховуючи пари края-грань з точки зору обличчя, є \(4f_4+6f_6\) пари. З формули Ейлера ми бачимо, що кількість граней \(f\) має бути 5, так що тоді \(4f_4+6f_6 \geq 20\) . Але з нашого підрахунку крайових пар ми маємо \(2m=4f_4+6f_6\) , даючи \(18 \geq 20\) , що явно абсурдно. Таким чином, не \(K_\) є площинним. У цей момент ви, мабуть, запитуєте себе «Так що?» Ми вклали неабияку кількість зусиль, щоб встановити, що \(K_5\) і \(K_\) є неплощинними. Зрозуміло, що будь-який графік, який містить їх також непланарний, але є багато графіків, так що ви можете подумати, що ми могли б бути в цьому назавжди. На щастя, ми не будемо, оскільки за своєю суттю планарність дійсно зводиться до цих двох графіків, як ми скоро побачимо. Якщо \(G=(V,E)\) граф і \(uv \in E\) , то ми можемо сформувати новий граф, \(G′\) який називається , \(G\) додаючи нову вершину \(v′\) і \(uv\) замінивши ребро ребрами \(uv′\) і \(v′v\) . Іншими словами, \(G′\) має набір вершин \(V′=V \cup \\) та набір країв \(E′=(E−\) \cup \\) . Два графіка \(G_1\) і \(G_2\) є , якщо їх можна отримати з одного і того ж графіка шляхом (потенційно тривіальної) послідовності елементарних підрозділів. Мета обговорення гомеоморфних графіків полягає в тому, що два гомеоморфні графіки мають однакові властивості, коли мова йде про малювання в площині. Щоб побачити це, подумайте про те, що станеться, \(K_5\) якщо ми сформуємо елементарний підрозділ його через будь-який з його країв. Ясно, що він залишається неплощинним. Насправді, якщо взяти будь-який неплоский граф і сформувати елементарний підрозділ, використовуючи будь-який з його ребер, отриманий граф буде неплощинним. Наступна дуже глибока теорема була доведена польським математиком Казимежем Куратовським в 1930 році. Його доказ виходить за рамки цього тексту.

Теорема 5.34. Теорема Куратовського

Графік є планарним тоді і лише тоді, коли він не містить підграф гомеоморфний ні \(K_5\) або \(K_<3,3>\) .

Теорема Куратовського дає корисний спосіб перевірки, чи є граф планарним. Хоча знайти підграф гомеоморфний до \(K_5\) або \(K_<3,3>\) вручну не завжди легко, існують ефективні алгоритми для тестування планарності, які використовують цю характеристику. Щоб побачити цю теорему в роботі, розглянемо графік Петерсена, показаний на малюнку 5.17. Граф Петерсена має 10 вершин і 15 ребер, тому він проходить тест теореми 5.33, і наш аргумент, використовуючи формулу Ейлера, щоб довести, що \(K_<3,3>\) це непланарний був досить складним, ми, ймовірно, не хочемо спробувати його для графа Петерсена. Щоб використати теорему Куратовського тут, нам потрібно вирішити, чи вважаємо за краще знайти підграф гомеоморфний до \(K_5\) чи до \(K_<3,3>\) . Хоча графік Петерсена виглядає дуже схожим на \(K_5\) , він насправді одночасно занадто схожий і занадто різний для нас, щоб мати можливість знайти підграф гомеоморфний до \(K_5\) , оскільки кожна вершина має ступінь 3. Таким чином, ми поставили собі за мету знайти підграф графа Петерсена гомеоморфний до \(K_<3,3>\) . Для цього зверніть увагу, що \(K_<3,3>\) містить цикл довжини 6 і три ребра, які знаходяться на місці між вершинами навпроти один одного на циклі. Ми ідентифікуємо шестицикл в графі Петерсена і малюємо його як шестикутник і поміщаємо решту чотири вершини всередині циклу. Такий креслення показаний на малюнку 5.35. Підграф \(K_<3,3>\) гомеоморфний до знайдено шляхом видалення чорної вершини, оскільки тоді білі вершини мають ступінь два, і ми можемо замінити кожну з них та їх два падаючі ребра (показано жирним шрифтом) одним ребром. Малюнок 5.35. Більш наочний малюнок графа Петерсена Ми закриваємо цей розділ проблемою, яка об’єднує поточний розділ разом з темою розфарбовування графіка. У 1852 році Френсіс Гатрі, англієць, який в той час навчався на юриста, але згодом став професором математики в Південній Африці, намагався розфарбувати карту графств Англії так, щоб будь-які два округи, які поділяли межовий сегмент (тобто вони торкнулися більш ніж однієї точки) були пофарбовані різними кольорами. Він помітив, що для цього йому потрібні лише чотири кольори, і він не зміг намалювати жодної карти, яка потребує п’яти кольорів. (Він зміг знайти карту, яка вимагала чотирьох кольорів, приклад якої показаний на малюнку 5.36.) Малюнок 5.36. Карта, яка вимагає чотирьох кольорів Чи може бути правдою, що кожна карта може бути пофарбована лише чотирма кольорами? Він запитав про проблему свого брата Фредеріка Гатрі, який був студентом математики Університетського коледжу в Лондоні, і Фредерік врешті-решт повідомив проблему Августу де Моргану (про славу законів де Моргана), одному зі своїх викладачів. Саме таким чином народилася одна з найвідоміших (або сумнозвісних) проблем, відома протягом століття як Проблема чотирьох кольорів, а тепер теорема про чотири кольори, в теорії графів. Де Морган дуже зацікавився проблемою чотирьох кольорів, і передав її серу Вільяму Роуану Гамільтону, видатному ірландському математику і тому, для кого названі гамільтонові цикли, але Гамільтон не знайшов проблему цікавою. Гамільтон – один з небагатьох людей, які розглядали проблему чотирьох кольорів, але не захопилися нею. Ми продовжимо наше обговорення історії теореми чотирьох кольорів за мить, але спочатку ми повинні розглянути, як ми можемо перетворити проблему розфарбовування карти на питання теорії графів. Що ж, здається природним, що кожному регіону повинна бути присвоєна відповідна вершина. Ми хочемо змусити регіони, які поділяють межу, мати різні кольори, тому це говорить про те, що ми повинні розмістити ребро між двома вершинами, якщо і тільки якщо їх відповідні області мають спільну межу. (Як приклад, карта на рис. 5.36 відповідає графіку \(K_4\) .) Неважко побачити, що це створює плоский графік, оскільки ми можемо провести ребра через загальний межовий відрізок. Крім того, трохи подумавши, ви повинні побачити, що за умови плоского креслення графіка, ви можете створити карту, в якій кожна вершина веде до області, а ребра ведуть до загальних сегментів кордону. Таким чином, проблема чотирьох кольорів може бути зазначена як «Чи кожен планарний графік має хроматичне число не більше чотирьох?» Інтерес до проблеми чотирьох кольорів нудився до 1877 року, коли британський математик Артур Кейлі написав листа Королівському товариству з проханням про те, чи була вирішена проблема. Це принесло проблему до уваги ще багатьох людей, і перше «доказ» теореми чотирьох кольорів, завдяки Альфреду Брею Кемпе, було завершено в 1878 році і опубліковано через рік. Минуло 11 років, перш ніж Персі Джон Хівуд знайшов недолік у доказі, але зміг врятувати його достатньо, щоб показати, що кожен планарний графік має хроматичне число не більше п’яти. У 1880 році Пітер Гатрі Тайт, британський фізик, найвідоміший своєю книгою Трактат про природну філософію з сером Вільямом Томсоном (лорд Кельвін), зробив оголошення, яке припустило, що він мав доказ теореми чотирьох кольорів, що використовують гамільтонівські цикли в певних планарних графіках. Однак, відповідно до того, як Тайт наближався до деяких домислів у математичній теорії вузлів, виявляється, що згодом він зрозумів близько 1883 року, що він не міг довести, що гамільтонівські цикли, які він використовував, насправді існували, і тому Тайт, ймовірно, лише вважав, що він має доказ теореми чотирьох кольорів. на короткий час, якщо взагалі. Однак потрібно було б до 1946 року, щоб знайти контрприклад до здогадки, яку Тайт використовував у своїй спробі довести теорему чотирьох кольорів. У першій половині ХХ століття був досягнутий певний поступовий прогрес у вирішенні проблеми чотирьох кольорів, але мало хто з видатних математиків серйозно зацікавився нею. Останній поштовх для підтвердження теореми чотирьох кольорів прийшов приблизно в той же час, коли перші електронні комп’ютери набули широкого використання в промисловості та дослідженнях. У 1976 році два математики з Університету штату Іллінойс оголосили про своє комп’ютерне доказ теореми чотирьох кольорів. Доказ Кеннета Аппела та Вольфганга Хакена змусив Університет штату Іллінойс додати фразу «ЧОТИРИ КОЛЬОРИ ДОСТАТНЬО» до відбитка свого поштового лічильника.

Теорема 5.37. Теорема про чотири кольори

4.S: Теорія графів (резюме)

Не дивно, що ці питання часто пов’язані один з одним. Наприклад, хроматичне число графа не може бути більшим за 4, коли графік плоский. Чи має граф шлях Ейлера, залежить від того, до якої кількості вершин прилягає кожна вершина (і чи завжди ці числа є парними чи ні). Навіть існування збігів у двосторонніх графах можна довести за допомогою контурів.

Огляд глави

1

Які (якщо такі є) з наведених нижче графіків однакові? Які бувають різні? Поясніть.

Перший і третій графіки однакові (спробуйте перетягувати вершини навколо, щоб зображення збігалися), але середній графік відрізняється (що ви можете побачити, наприклад, зазначивши, що середній граф має лише одну вершину ступеня 2, а інші мають дві такі вершини).

2

Який із графіків у попередньому питанні містить шляхи чи схеми Ейлера? Які з графіків є площинними?

Перший (і третій) графіки містять шлях Ейлера. Всі графіки плоскі.

3

Намалюйте графік, який має схему Ейлера, але не є плоскою.

4

Намалюйте графік, який не має шляху Ейлера, а також не є площинним.

5

Якщо граф має 10 вершин і 10 ребер і містить схему Ейлера, він повинен бути планарним? Скільки облич у нього було б?

Так. За формулою Ейлера у нього було б 2 обличчя. Це робить. Єдиним таким графом є \(C_\text<.>\)

6

Припустимо, \(G\) це граф з \(n\) вершинами, кожна з яких має ступінь 5.

Для яких значень це \(n\) має сенс?
Для яких значень \(n\) графа має шлях Ейлера?
Яке найменше значення, \(n\) для якого графік може бути планарним? (хитрий)

Тільки якщо \(n \ge 6\) and is even.
Жодного.
12. Такий графік мав би \(\frac\) edges. If the graph is planar, then \(n – \frac+ f = 2\) so there would be \(\frac\) faces. Also, we must have \(3f \le 2e\text\) since the graph is simple. So we must have \(3\left(\frac\right) \le 5n\text\) Solving for \(n\) gives \(n \ge 12\text\)

7

На шкільному танці 6 дівчаток і 4 хлопчика по черзі танцюють (як пари) один з одним.

Скільки пар танцювали, якщо кожна дівчина танцює з кожним хлопчиком?
Скільки пар танцювали, якщо всі танцювали з усіма іншими (незалежно від статі)?
Поясніть, які графіки можна використовувати для представлення цих ситуацій.

Було 24 пари: 6 варіантів для дівчинки і 4 варіанти для хлопчика.
Було 45 пар: \(\) since we must choose two of the 10 people to dance together.
Для частини (а) відраховуємо кількість ребер в \(K_\text\) In part (b) we count the edges of \(K_\text\)

8

Серед групи \(n\) людей, чи можна всім дружити з непарною кількістю людей в групі? Якщо так, то що можна сказати про \(n\text\)

Так, до тих пір, поки \(n\) is even. If \(n\) were odd, then corresponding graph would have an odd number of odd degree vertices, which is impossible.

9

Ваш друг кинув виклик вам створити опуклий багатогранник, що містить 9 трикутників і 6 п’ятикутників.

Чи можна побудувати такий багатогранник, використовуючи тільки ці форми? Поясніть.
Ви вирішили також включити один гептагон (семисторонній багатокутник). Скільки вершин містить ваш новий опуклий багатогранник?
Припускаючи, що ви успішно будуєте свій новий 16-гранний багатогранник, чи може кожна вершина бути з’єднанням однакової кількості граней? Чи може кожна вершина приєднатися до 3 або 4 граней? Якщо так, то скільки буде кожного типу вершини?

Ні. У 9 трикутників кожен вносить 3 ребра, а 6 п’ятикутників – 5 країв. Це дає загалом 57, що рівно вдвічі більше кількості ребер, оскільки кожне ребро межує рівно 2 грані. Але 57 – це непарно, так що це неможливо.
Тепер складання всіх країв усіх 16 багатокутників дає загалом 64, тобто в багатограннику буде 32 ребра. Потім ми можемо використовувати формулу Ейлера \(v – e + f = 2\) to deduce that there must be 18 vertices.
Якщо скласти всі вершини з кожного багатокутника окремо, то отримаємо в цілому 64. Це не ділиться на 3, тому не може бути, що кожна вершина належить рівно 3 граням. Чи могли вони всі належати до 4 осіб? Це означало б, що були \(64/4 = 16\) vertices, but we know from Euler’s formula that there must be 18 vertices. We can write \(64 = 3x + 4y\) and solve for \(x\) and \(y\) (as integers). We get that there must be 10 vertices with degree 4 and 8 with degree 3. (Note the number of faces joined at a vertex is equal to its degree in graph theoretic terms.)

10

Чи існує опуклий багатогранник, який вимагає 5 кольорів для правильного фарбування вершин багатогранника? Поясніть.

Ні. Кожен багатогранник може бути представлений у вигляді плоского графа, а теорема чотирьох кольорів говорить, що кожен планарний граф має хроматичне число не більше 4.

11

Скільки ребер \(K_\) має графік? Для яких значень графіка \(n\) містить схему Ейлера? Для яких значень графа \(n\) є планарним?

\(K_\) has \(n^2\) edges. The graph will have an Euler circuit when \(n\) is even. The graph will be planar only when \(n \lt 3\text<.>\)

12

Графік \(G\) має 6 вершин з \(1, 2, 2, 3, 3, 5\text<.>\) градусами Скільки ребер \(G\) має? \(G\) Якби планарна, скільки граней вона мала б? Чи \(G\) є шлях Ейлера?

\(G\) has 8 edges (since the sum of the degrees is 16). If \(G\) is planar, then it will have 4 faces (since \(6 – 8 + 4 = 2\) ). \(G\) does not have an Euler path since there are more than 2 vertices of odd degree.

13

Яка найменша кількість кольорів вам потрібно, щоб правильно розфарбувати вершини Чи \(K_\text<.>\) можете ви сказати, чи \(K_7\) є плоскою на основі вашої відповіді?

\(7\) colors. Thus \(K_7\) is not planar (by the contrapositive of the Four Color Theorem).

14

Яка найменша кількість кольорів вам потрібно, щоб правильно розфарбувати вершини Чи \(K_\text\) можете ви сказати, чи \(K_\) є плоскою на основі вашої відповіді?

Хроматичне число \(K_\) is 2, since the graph is bipartite. You cannot say whether the graph is planar based on this coloring (the converse of the Four Color Theorem is not true). In fact, the graph is not planar, since it contains \(K_\) as a subgraph.

15

Додекаедр – це правильний опуклий багатогранник, що складається з 12 правильних п’ятикутників.

Припустимо, ви розфарбовуєте кожен п’ятикутник одним з трьох кольорів. Доведіть, що повинні бути два сусідніх п’ятикутника пофарбовані однаково.
Що робити, якщо використовувати чотири кольори?
Що робити, якщо замість додекаедра ви пофарбували грані куба?

Для всіх цих питань ми дійсно розфарбовуємо вершини графа. Ви отримуєте графік, спочатку намалювавши планарне зображення багатогранника, а потім взявши його плоский подвійний: поставте вершину в центр кожної грані (включаючи зовнішню) і з’єднайте дві вершини, якщо їх грані поділяють ребро.

Оскільки плоский подвійний додекаедр містить 5-колесо, його хроматичне число становить щонайменше 4. Крім того, припустимо, що ви можете розфарбувати обличчя, використовуючи 3 кольори без будь-яких двох сусідніх граней, пофарбованих однаково. Візьміть будь-яке обличчя і пофарбуйте його в синій колір. П’ятикутники, що межують з цим синім п’ятикутником, не можуть бути пофарбовані в синій колір. Пофарбуйте перший в червоний колір. Два його сусіди (примикають до синього п’ятикутника) отримують кольоровий зелений колір. Решта 2 не можуть бути синіми або зеленими, але також не можуть бути червоними, оскільки вони сусідять один з одним. Таким чином, потрібен 4-й колір.
Планарний двійник додекаедра сам по собі є планарним графом. Таким чином, за 4-колірною теоремою, він може бути забарвлений, використовуючи лише 4 кольори без однакового забарвлення двох суміжних вершин (відповідних граням багатогранника).
Куб може бути правильно 3-х кольоровим. Пофарбуйте «верх» і «низ» червоним, «спереду» і «ззаду» синім, а «лівий» і «правий» зелений.

16

Якщо плоский граф \(G\) з \(7\) вершинами ділить площину на 8 областей, скільки ребер має \(G\) мати?

\(G\) has \(13\) edges, since we need \(7 – e + 8 = 2\text<.>\)

17

Чи має графік шлях або ланцюг Ейлера? Поясніть.
Граф площинний? Поясніть.
Граф двосторонній? Завершити? Повний двосторонній?
Що таке хроматичне число графіка.

Графік має шлях Ейлера, але не схему Ейлера. Є рівно дві вершини з непарним ступенем. Шляхи починаються з одного і закінчуються в іншому.
Графік площинний. Незважаючи на те, що він малює краю хрест, його легко перемалювати без перетину країв.
Графік не двосторонній (є непарний цикл), ні повний.
Хроматичне число графа дорівнює 3.

18

Для кожної частини нижче скажіть, чи є твердження істинним чи хибним. Поясніть, чому справжні твердження правдиві, і наведіть зустрічніприклади для неправдивих висловлювань.

Кожен двосторонній граф площинний.
Кожен двосторонній граф має хроматичне число 2.
Кожен двосторонній граф має шлях Ейлера.
Кожна вершина двостороннього графа має парний ступінь.
Граф є двостороннім тоді і тільки тоді, коли сума ступенів усіх вершин парна.

Помилкові. Наприклад, \(K_\) is not planar.
Правда. Граф є двостороннім, тому можна розділити вершини на дві групи без ребер між вершинами в одній групі. Таким чином, ми можемо пофарбувати всі вершини однієї групи червоним, а інший групи синім.
Помилкові. \(K_\) has 6 vertices with degree 3, so contains no Euler path.
Помилкові. \(K_\) again.
Помилкові. Сума ступенів всіх вершин є парною для всіх графів, тому ця властивість не означає, що граф є двостороннім.

19

Розглянемо твердження «Якщо граф плоский, то він має шлях Ейлера».

Напишіть зворотне твердження.
Напишіть контрапозитив заяви.
Напишіть заперечення заяви.
Чи можна контрапозитив бути помилковим? Якби це було, що б це вам розповіло?
Оригінальне твердження вірне чи хибне? Доведіть свою відповідь.
Зворотне твердження вірне чи хибне? Доведіть свою відповідь.

Якщо граф має шлях Ейлера, то він плоский.
Якщо граф не має шляху Ейлера, то він не є площинним.
Існує графік, який є планарним і не має шляху Ейлера.
Так. Насправді в цьому випадку це відбувається тому, що оригінальне твердження є помилковим.
Помилкові. \(K_4\) is planar but does not have an Euler path.
Помилкові. \(K_5\) has an Euler path but is not planar.

20

Пам’ятайте, що – це зв’язаний графік без циклів.

Припустіть зв’язок між вершинами та ребрами графа дерева. (Наприклад, чи можете ви мати дерево з 5 вершинами та 7 ребрами?)
Поясніть, чому кожне дерево з принаймні 3 вершинами має листок (тобто вершину ступеня 1).
Доведіть свою здогадку з частини (а) шляхом індукції на кількість вершин. Підказка: Для індуктивного кроку ви припускаєте, що ваша гіпотеза вірна для всіх дерев з \(k\) вершинами, і показати, що вона також вірна для довільного дерева з \(k+1\) вершинами. Розглянемо, що відбувається, коли ви обрізаєте лист, а потім даєте йому відрости.

Який граф є планарним