Graf je souvislý, pokud mezi každými dvěma z jeho vrcholů vede cesta. To znamená, že všechny vrcholy jsou spolu nějak propojené –⁠ dokážeme v grafu přejít po hranách z každého vrcholu do všech ostatních.

Komponenta souvislosti je část grafu, která je souvislá, ale pokud bychom do ní chtěli zahrnout nějaké další hrany nebo vrcholy, souvislá by být přestala. Každý graf je rozdělený na několik komponent souvislosti. Pokud je graf souvislý, tvoří sám o sobě jednu komponentu souvislosti. Graf na obrázku není souvislý a skládá se ze 4 komponent souvislosti, jedna z nich je vyznačená žlutě.

Podgraf je část (tedy některé vybrané vrcholy a hrany) grafu, která sama o sobě také tvoří graf. Každá hrana v podgrafu tedy musí mít na obou svých koncích vrchol, který také patří do podgrafu. Žluté vrcholy a hrany na obrázku tvoří podgraf.

V úplném grafu je každý vrchol je spojený s každým. Tento graf má tedy maximální počet hran, který může mít.

Strom je souvislý graf, který neobsahuje žádnou kružnici (cyklus) jako podgraf. Stromy mají mnoho zajímavých vlastností (např. mezi každými dvěma vrcholy vede právě jedna cesta) a často se v informatice používají (např. pro přehledné a efektivní uložení dat).