Riešenie: Prvá postupnosť nie je grafová, pretože v grafe musí byť počet vrcholov nepárneho stupňa párny, čo v tomto prípade neplatí. Tu je počet nepárnych čísel 3.
Druhá postupnosť tiež nie je grafová, lebo v grafe s \(n\) vrcholmi je maximálny možný stupeň vrcholu \(n-1\). Pre 8 vrcholov je teda maximálny možný stupeň 7.
Obidve predchádzajúce podmienky sú splnené, počet vrcholov nepárneho stupňa je 4, teda párny a maximálny možný stupeň je 7, čo nie je porušené. Platí, že pôvodná postupnosť je grafová práve vtedy, ak je grafová aj postupnosť, ktorú z nej dostaneme takto:

1. Zoradíme čísla na nerastúcu postupnosť.
2. Vynecháme prvé číslo k a od k nasledujúcich čísel odpočítame jednotku.
3. Postupnosť znovu zoradíme a tento postup opakujeme dovtedy, pokiaľ nedostaneme postupnosť, o ktorej vieme ľahko rozhodnúť, či je, alebo nie je grafová.

Diagram takéhoto grafu už vieme nakresliť, teda postupnosť je grafová. Diagram pôvodného grafu môže vyzerať napríklad takto:

Riešenie: Kvôli lepšiemu prehľadu a zdôvodňovaniu si najprv všetky vrcholy grafov označíme: Ako prvý krok urobíme to, že v každom grafe zistíme počet vrcholov a hrán. Pre dva izomorfné grafy totiž platí, že musia mať rovnaký počet vrcholov aj hrán. Nesmieme však zabúdať na to, že je to iba nutnou, nie postačujúcou podmienkou. V našom prípade je v každom grafe počet vrcholov 5 a počet hrán 6. Takže na základe toho nie je možné žiaden graf vylúčiť. Keď sa však pozrieme na \(G_2\), zistíme, že ide o multigraf, pretože z vrcholu \(f\) do vrcholu \(j\) máme dvojnásobnú hranu. To v ostatných grafoch nie je, preto \(G_2\) nie je izomorfný so žiadnym z ostatných grafov. Vo všetkých grafoch máme po dva vrcholy, ktoré incidujú s tromi hranami a po tri vrcholy, ktoré incidujú s dvomi hranami. No v grafe \(G_1\) vrcholy incidujúce s tromi hranami \((d, e)\) nemajú spoločnú hranu, kým v grafoch \(G_3\), \(G_4\) tieto vrcholy majú spoločnú hranu \(\{m,o\};\{r,u\}\). Preto ani graf \(G_1\) nie je incidentný so žiadnym iným grafom. V grafoch \(G_3\), \(G_4\) sú zhodné počty vrcholov, hrán, vzájomných incidencií, ale napríklad aj počty kružníc. Pokúsime sa teda nájsť izomorfizmus zobrazujúci tieto grafy navzájom: \[f: G_3 \to G_4; f=\left ( \begin{array}{c} n\\ p \end{array} \begin{array}{c} o\\ r \end{array} \begin{array}{c} m\\ u \end{array} \begin{array}{c} k\\ s \end{array} \begin{array}{c} l\\ t \end{array}\right ) \] Ľahko možeme ukázať, že diagram grafu \(G_4\) sa dá prekresliť tak ako diagram grafu \(G_3\). Toto nemusí byť jediný možný izomorfizmus. Grafy \(G_3\), \(G_4\) sú izomorfné, čo zapisujeme aj \(G_3 \cong G_4\).

Riešenie: Vzdialenosť dvoch vrcholov v grafe je dĺžka najkratšej cesty spájajúcej tieto dva vrcholy. V nasledujúcej tabuľke sú zapísané vzdialenosti všetkých vrcholov od vrcholu \(v_1\): \[ \left | \begin{array}{r} d(v_1,v_1)=0\\ d(v_1,v_2)=1\\ d(v_1,v_3)=2\\ d(v_1,v_4)=3\\ d(v_1,v_5)=1 \end{array}\right . \left | \begin{array}{r} d(v_1,v_6)=1\\ d(v_1,v_7)=2\\ d(v_1,v_8)=3\\ d(v_1,v_9)=2\\ d(v_1,v_{10})=3 \end{array}\right | \] Ako vidieť v tabuľke, vrcholy \(v_4\), \(v_8\) a \(v_{10}\) majú z vrcholu \(v_1\) vzdialenosť 3.

Riešenie: Excentricita vrcholu \(v_i\) v grafe \(G\), označujeme ju \(e(v_i,G)\), je číslo, ktoré sa rovná maximálnej vzdialenosti z daného vrcholu do nejakého iného vrcholu. Podľa toho je \(e(v1,G)=3\), pretože maximálna vzdialenosť z vrcholu \(v_1\) v grafe \(G\) je 3 (viď tabuľku v predchádzajúcom príklade). Podobne určíme aj ostatné excentricity: \[ \left | \begin{array}{r} e(v_1,G)=3\\ e(v_2,G)=3\\ e(v_3,G)=3\\ e(v_4,G)=4\\ e(v_5,G)=4 \end{array}\right . \left | \begin{array}{r} e(v_6,G)=2\\ e(v_7,G)=3\\ e(v_8,G)=3\\ e(v_9,G)=3\\ e(v_{10},G)=3 \end{array}\right | \] Polomer grafu \(r(G)\) je číslo rovnajúce sa minimálnej hodnote excentricity v grafe \(G\). V našom prípade \(r(G)=2\).
Priemer grafu \(P(G)\) je číslo rovnajúce sa maximálnej hodnote excentricity v danom grafe \(G\). V tomto príklade je \(P(G)= 4\). (Pozn.: Priemer grafu nemusí byť dvojnásobkom polomeru grafu.)
Stred grafu \(S(G)\) je množina všetkých vrcholov grafu, ktorých excentricita je rovná polomeru. V tomto prípade \(S(G)=\{v_6\}\). (Pozn.: Stred grafu nemusí byť jeden vrchol, môže ho tvoriť niekoľko vrcholov, alebo aj všetky vrcholy, napríklad v kompletných grafoch.)

Riešenie: Jednou zo základných vlastnosti stromu je, že \(|H|=|V|-1\). Teda ak je počet vrcholov grafu 9, počet jeho hrán bude 8. A každá hrana sa do súčtu stupňov vrcholov započítava dvakrát (s obidvoma vrcholmi, ktoré s ňou incidujú), takže strom s 9 vrcholmi bude mať súčet stupňov 16.
Analogicky, ak počet vrcholov je \(n\), počet hrán bude \(n-1\) a súčet stupňov vrcholov je \(2(n-1)\).

Riešenie: V strome môžeme hľadať polomer, priemer a stred jednoduchšie ako u iných grafov. Najprv vynecháme vrcholy stupňa 1 aj s hranami, ktoré s nimi incidujú. Dostaneme opäť strom: Tento postup zopakujeme znova, dovtedy, kým nám nezostane jeden vrchol, alebo dva vrcholy s incidentnou hranou: Vrchol \(i\), ktorý nám ostal, tvorí stred grafu (ak by ostali dva vrcholy, tvorili by oba vrcholy stred).
Polomer grafu je rovný počtu iterácii (odobratie hrán), ktoré sme vykonali, teda \(r=4\) (ak by stred pozostával z dvoch vrcholov, polomer je počet iterácii plus jedna).
Priemer grafu je \(P= 2r\), v našom prípade \(P=8\) (v prípade dvoch stredových vrcholov je \(P=2r-1\) ).

Riešenie: Podobne ako v predchádzajúcej úlohe použijeme iterácie založené na odoberaní vrcholov stupňa jeden. Vrcholy \(f,i\), ktoré nám ostali, tvoria stred grafu.
Keďže stred tvoria dva vrcholy, polomer grafu je rovný počtu iterácii plus jedna \(r=3\).
Priemer grafu je \(P= 2r-1=5\).

Riešenie: Koreňovým stromom nazývame taký orientovaný strom, ktorý obsahuje koreň, teda vrchol, z ktorého existuje dráha do každého ďalšieho vrcholu. Z daných orientovaných stromov sú koreňovými stromy \( T_2, T_3\). V nasledujúcich diagramoch sú korene označené písmenom \(k\).
Binárnym nazývame taký koreňový strom, v ktorom platí, že každý vrchol má vonkajší stupeň buď \( 0\) alebo \(2\). Takým je len strom \(T_3\).
Hĺbka binárneho stromu je excentricita jeho koreňa, v strome \(T_3\) je to \(5\).