---
# System prepended metadata

title: MDL Lista 14
tags: [MDL]

---

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

## Zadanie 1
![](https://i.imgur.com/O7OZzTH.png)

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
![](https://i.imgur.com/Yfs6AYj.png)

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

![](https://i.imgur.com/Ex6O7Ak.png)
- Dla $k=3$ kostka jest planarna:
![](https://i.imgur.com/vGvr5L3.png)
- Dla $k=4$ nie jest 
![](https://i.imgur.com/qAR6Rrn.png)    
    -> 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
![](https://i.imgur.com/GZ4uAqs.png)

![](https://i.imgur.com/LvurQKG.png)
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
![](https://i.imgur.com/m3ztuEo.png)

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.

