Johdatus diskreettiin matematiikkaan, syksy 2000
Harjoitus 8, 14.-16.11.

1. 1. Olkoon $G = (V,E)$ vähintään 3-solmuinen yhtenäinen tasoverkko, jonka kaikki syklit ovat vähintään neljän pituisia (so. verkko ei sisällä $K_3$-muotoista indusoitua aliverkkoa eli on kolmioton). Osoita, että $G$:n kaarien määrää rajoittaa tällöin epäyhtälö $\vert E\vert \leq 2\vert V\vert-4$. (Kuten luennolla esitettiin, ilman kolmiottomuusoletusta saadaan heikompi epäyhtälö $\vert E\vert \leq 3\vert V\vert-6$.)
   2. Osoita edellisen tuloksen nojalla, että verkko $K_{3,3}$ ei ole planaarinen, ja että edellisissä harjoituksissa tarkastellut hyperkuutioverkot $H_n$ ovat planaarisia, jos ja vain jos $n \leq 3$.

2. 1. Mikä on harjoituksissa 6 tarkastellun ns. Petersenin verkon väriluku?
   2. Montako väriä enintään tarvitaan avaruuden konveksin monitahokkaan (esim. kuution, pyramidin, ikosaedrin tms.) sivutahkojen värittämiseen niin, ettei millekään kahdelle vierekkäiselle (= yhteisen särmän erottamalle) tahkolle tule samaa väriä?

3. Eräs yliopisto järjestää samalla lukukaudella kurssit TTP, JDM, ALTE, APK, DL ja MIT. Kursseilla TTP ja APK on yhteisiä opiskelijoita, samoin kuin kursseilla APK/JDM, JDM/DL, DL/ALTE ja ALTE/MIT. Montako koepäivää tarvitaan kurssien kokeisiin, jotta kellekään opiskelijalle ei tule päällekkäisiä kokeita?

4. Pieni hiiri haluaa syödä kuutionmuotoisen juuston. Ollen järjestelmällinen eläin, hiiri jakaa mielessään juuston 3$\times$3$\times$3 alikuutioon ja päättää edetä niin, että aloittaa syömisen yhdestä nurkasta, syö kokonaisen alikuution kerralla, etenee siitä johonkin naapurikuutioon, ja syö viimeisenä juuston ytimessä olevan keskikuution. Onnistuuko hiiren suunnitelma?

5. 1. Verkko G on $d$-säännöllinen, jos sen jokaisen solmun asteluku on tasan $d$. Osoita, että jokaisessa $d$-säännöllisessä kaksijakoisessa verkossa voidaan muodostaa täydellinen pariutus.
   2. Kaikkien 15 EU-maan pääministerit saapuvat Jyväskylään huippukokoukseen tapaamaan 15:ta Jyvässeudun merkittävää kunnallista vaikuttajaa. Kukin pääministeri saa nimetä kolme vaikuttajaa, joiden kanssa hän haluaisi neuvotella. Osoita, että mikäli kenellekään jyvässeutulaiselle ei tule enempää kuin kolme neuvottelupyyntöä (tällöin itse asiassa jokaiselle tulee tasan kolme), kaikki toivotut tapaamiset voidaan järjestää kolmessa peräkkäisessä vaiheessa, joissa kussakin käydään 15 pareittaista neuvottelua EU:n ja Jyvässeudun edustajien kesken.

6. Olkoon ${\cal A} = \{A_1,\dots,A_n\}$ kokoelma jonkin äärellisen perusjoukon $U$ osajoukkoja. Perheen ${\cal A}$ edustajisto on $n$-alkioinen joukko $S \subseteq U$, joka sisältää täsmälleen yhden alkion kustakin joukosta $A_i$, $i = 1,\dots,n$. (Huomaa siis, että vaikka joukot $A_i$ eivät välttämättä ole erillisiä, niin sama alkio ei voi edustaa useampaa joukkoa.) Osoita, että perheestä ${\cal A}$ voidaan valita edustajisto, jos ja vain jos kaikilla $r = 1,\dots,n$ on minkä tahansa $r$:n $A$-joukon yhdisteessä vähintään $r$ alkiota, so.
   
   $$\vert A_{i_1} \cup \dots \cup A_{i_r}\vert \geq r,$$
   
   
   kaikilla $A_{i_1},\dots,A_{i_r}$, missä $i_j \neq i_k$, kun $j \neq k$. (Vihje: Pariutus.)