Riešenie: Graf \(\bar{G}\) je komplementárnym grafom ku grafu \(G\), bude teda obsahovať tie isté vrcholy ako graf \(G\) a všetky hrany chýbajúce v grafe \(G\) k tomu, aby bol kompletný.
Aby sme dostali graf \(\bar{G}-v\), tak z grafu \(\bar{G}\) odstránime vrchol\(v\) a všetky hrany, ktoré s nim incidujú.

Riešenie: Graf \(\bar{G}\) je komplementárnym grafom ku grafu \(G\), teda podobne ako v prdchádzajúcom príklade, bude obsahovať tie isté vrcholy ako graf \(G\) a všetky hrany chýbajúce v grafe \(G\) k tomu, aby bol kompletný.
Graf \(G \cap H\) sa nazýva prienikom grafov \(G, H\). Obsahuje všetky tie vrcholy, ktoré sa vyskytujú súčasne v oboch grafoch a tiež všetky hrany vyskytujúce sa v oboch grafoch.
\(G \cup H\)je graf, ktorý je zjednotením grafov \(G, H\). Bude obsahovať všetky vrcholy aj hrany nachádzajúce sa aspoň v jednom z týchto grafov.
Graf \(G \oplus H\) sa nazýva symetrickou diferenciou grafov \(G, H\). Je definovaný vzťahom: \(G \oplus H=(G \cup H)-(G \cap H)\). Teda zostrojíme si najprv graf \(G \cup H\), potom \(G \cap H\) a ich rozdiel je graf \(G \oplus H\).

Riešenie: Nakreslíme diagramy všetkých takýchto podgrafov (vrcholy na tej istej pozícii budeme považovať za rovnako označené). Všetkých podgrafov grafu \(G\), ktoré neobsahujú izolovaný vrchol je šestnásť, diagramy pätnástich sú nakreslené, šestnásty je prázdny graf.
Faktor grafu je podgraf daného grafu, ktorý obsahuje všetky vrcholy ako daný graf. Z uvedených podgrafov je teda 5 faktorov. Sú to: 1., 3., 4., 5., 6.

Riešenie: Pod pojmom kvadratický faktor grafu rozumieme faktor, ktorého stupeň každého vrchola je 2. Keďže má ísť o rozklad grafu na dva kvadratické faktory, každý vrchol grafu musí mať stupeň 4. Z toho dôvodu je jasné, že graf \(J\) sa takto nedá rozložiť. Pre graf \(G\) na obrázku uvádzame dva roklady, v prvom prípade je jeden faktor súvislý, jeden nesúvislý, v druhom prípade sú oba faktory súvislé. Graf \(H\) sa dá na dva kvadratické faktory rozložiť len jedným spôsobom.

Riešenie:
a) Napríklad hociktorý kompletný graf, na obrázku je znázornený kompletný graf na 5 vrcholoch a kubický graf (všetky stupne sú 3) na 6 vrcholoch.
b) Taký graf neexistuje. Zdôvodnenie: Ak máme graf s \(n\) vrcholmi, minimálny stupeň vrchola je 0 a maximálny je \(n-1\). Ak však niektorý vrchol má stupeň 0, už tam nemôže byť vrchol stupňa \(n-1\) a naopak. Buď teda máme stupne \(0, ... ,n-2\), alebo \(1, ... ,n-1\). Všetkých možných stupňov je \(n-1\) a počet vrcholov je \(n\), čo znamená, že musia existovať aspoň dva vrcholy s rovnakým stupňom.

Riešenie: a) b) Vnútorný stupeň vrchola \(\delta^+\) je počet hrán, ktoré do vrchola vchádzajú (vonkajší stupeň vrchola \(\delta^-\) je počet hrán, ktoré z vrchola vychádzajú). Takže môže to byť napríklad takýto diagram. c) Prameň je vrchol, pre ktorý platí: \(\delta^+=0, \delta^-\geq0\), teda vrchol, z ktorého hrany len vychádzajú. Naopak pre ústie platí: \(\delta^+\geq0, \delta^-=0\), teda hrany do neho len vchádzajú. List (alebo tzv. visiaci vrchol) je vrchol, pr ktorý platí \(\delta^+=0, \delta^-=1\).

Riešenie: a) Je to pravdivé tvrdenie, vyplýva priamo z toho, ako je digraf definovaný.
b) Nie je to pravdivé tvrdenie, odstránením orientácie v digrafe môže vzniknúť násobná hrana, teda nie graf, ale multigraf. Na nasledujúcom obtázku je uvedený príklad.
c) Každá orientovaná hrana v digrafe prináša jednotku do súčtu vnútorných stupňov, aj jednotku do súčtu vonkajších stupňov. Teda do súčtu všetkých stupňov prispieva dvomi a tak tento súčet je rovný dvojnásobku počtu hrán, takže je párny. Tvrdenie je pravdivé.
d) Toto tvrdenie nie je pravdivé, ako kontrapríklad slúži napríklad diagram nasledujúceho digrafu, v ktorom súčet vnútorných stupňov je 3 a teda nepárny.
e) V digrafe s \(n\) vrcholmi môže z jedného vrchola vychádzať maximálne \(n-1\) hrán (do každého ďalšieho vrcholu jedna). Do jedného vrchola môže vchádzať tiež maximálne \(n-1\) hrán (z každého ďalšieho vrcholu jedna). Každá hrana sa však zarátala dvakrát, raz ako vstupujúca, raz ako vystupujúca. Takto je teda počet hrán \(n(n-1+n-1):2=n(n-1)\) a teda tvrdenie nie je pravdivé.

Riešenie: a) Silne súvislý podgraf je taký, kde sa z každého vrcholu viem dostať do každého tak, že zachovávam orientáciu. V tomto prípade máme teda len dve možnosti.
b) Tu prichádzajú do úvahy práve tie orientácie, ktoré nie sú v prípade a). Musíme teda najprv vypočítať počet všetkých možných orientácií. Každej hrane môžeme priradiť dve orientácie, hrán je \(5\), takže všetkých možných orientácii je \(2^5\). Potom všetkých takých orientácií, kde vznikne silne nesúvislý digraf je \(2^5-2\).