---
title: MDL Lista 14
tags: MDL
author: Mateusz Reis
---
# MDL LISTA 14

## Zadanie 1

Chcemy pokazać że $n-m+f=k+1$ gdzie $k$ to liczba spójnych składowych. Weźmy graf $G=(V,E)$, który składa się z $k$ spójnych składowych. Wiemy że $n-m+f=2$ jeśli połączymy ze sobą spójne składowe przy użyciu $k-1$ krawędzi stworzymy spójny graf $G^{'}$ dla którego mamy
$$
n-(m+k-1)+f=2\\
n-m+f=2+k-1\\
n-m+f=k+1
$$

## Zadanie 2

Załóżmy że graf G jest planarny.
Wiemy że $m\leq3n-6$ gdzie $m=E(G)$ oraz
$$
E(G)+E(\overline{G})=E(K_n)=\frac{n(n-1)}{2} \implies E(\overline G)=\frac{n(n-1)}{2}-m
$$ gdzie
$V(G)=V(\overline G)=n$ wtedy
$$
\frac{n(n-1)}{2}-m\leq3n-6\,\,\, m = 3n-6\\
\frac{n(n-1)}{2}\leq6n-12\\
n^2-13n+24\leq0\\
\Delta=169-98=73\\
\sqrt{\Delta}=\sqrt{73}\\
n_1=\frac{13+\sqrt{73}}{2}\,\,\, n_2=\frac{13-\sqrt{73}}{2}\\
\lfloor{n_1}\rfloor=10\,\,\,\lfloor n_2\rfloor=3\\
$$

## Zadanie 3

- Dla $k=3$ kostka jest planarna:
- Dla $k=4$ nie jest
-> załóżmy niewprost że kostka $Q_4$ jest planarna wtedy musiała by spełniać warunek $e\leq2v-4$ (bo kostka nie zawiera cykli o długości 3) dla $k=4$ kostka ma $e=2^{4-1}*4$ oraz
$v=2^4$ wtedy nierówność wygląda tak: $32\leq16-4$ co oczywiście jest fałszem więc taka kostka nie jest planarna (dla każdego k większego od 4 kostka nie będzie planarna ponieważ
$Q_4$ jest jej podgrafem)

## Zadanie 4

source:https://www.researchgate.net/figure/Drawing-of-K-6-with-three-crossings_fig1_220533618

Powyżej został przedstawiony graf $K_6$ jeśli utworzymy graf $H$ zgodnie z poleceniem otrzymamy graf w którym jest $6$ wierzchołków i każdy z nich ma stopień $5$, podgrafem grafu $H$ jest graf $K_{3,3}$(graf Kuratowskiego), tak więc $H$ nie jest planarny.

## Zadanie 5

a)
- Wiemy że $2|E|=\sum \deg(v_i)$ wtedy
$$
|E|\leq 6n-12\\
2|E|\leq 6n-12\\
\sum\deg(v)\leq6n-12,\,\,\, n=\sum t_i, \,\,\, \sum\deg(v)=\sum t_ii\\
\sum t_ii\leq6\sum t_i-12\\
12\leq6\sum t_i-\sum t_ii\\
12\leq \sum(6-i)t_i
$$

b)
- suma którą przed chwilą pokazaliśmy jest największa gdy $i=1$ weźmy więc graf który ma $n-2$ wierzchołków o stopniu $6$ oraz $2$ wierzchołki o stopniu $1$ wtedy
$$
(6-1)*2+(6-6)(n-2)\geq12\\
10\geq12\\
$$

co doprowadza do sprzeczności tak więc potrzebujemy co najmniej 3 wierzchołków o stopniach co najwyżej 5.