◎オイラーグラフは，すべての辺を一度だけ通る閉じた小道が存在するグラフのことで，すべての頂点の次数が偶数ならばオイラーグラフである。つまり，オイラーグラフかどうかは簡単に調べることができる。
一方，ハミルトングラフは，すべての頂点を一度だけ通る閉じた道（閉路という）が存在するグラフのこと。オイラーグラフとよく似た定義であるが，与えられたグラフがハミルトングラフであるかどうかを判定するのは，一般には容易ではない。
◎いくつかの特殊な性質を持つグラフの定義
・完全グラフ...すべての２頂点間に辺があるグラフ。頂点数が m である完全グラフを Km と書く。
・k-正則グラフ...すべての頂点の次数が一定値 k であるグラフ。
・２部グラフ...頂点集合を二つに分割して，すべての辺の両端点が同じ部分集合にはないようにできるグラフ。［実は，第６章のグラフの彩色の言葉を使えば，2-彩色可能なグラフのことである。つまり，すべての辺の両端点には異なる色を塗るという条件で，すべての頂点に色を付ける（これを頂点彩色という）とき，２色で彩色が可能なグラフを２部グラフという。］
・木...閉路が存在しない連結グラフ。
☆上の定義を使うと，次のようなことが言える。
1) 完全グラフ Km は，(m−1)-正則グラフである。（図 5-7）
2) m (m > 2) 個の頂点をもつ連結な 2-正則グラフは閉路である。（図 5-8）
3) 完全２部グラフ Km,m は m-正則グラフである。（演習問題 5-10）
4) m 個の頂点をもつ木の辺は (m−1) 本である。（第６章で証明される）
□完全グラフや完全２部グラフにＫという記号を使うが，これは『完全』の頭文字のＫではない。第６章で登場するポーランドの数学者クラトフスキー (Casimir Kuratowski，1896-?，つまりいつ死んだか分からない）の名前に由来している。
◎同形でない木は全部で何種類あるか
頂点数が m の木の個数を T(m) と書くと，小さな m については次のようになる。
T(1) = T(2) = T(3) = 1，T(4) = 2，T(5) = 3
頂点数が５までの木については演習問題 5.11（p.107）
T(6) = 6（p.99 参照），T(7) = 11（補充問題5.21），T(8) = 23
☆補充問題 5.21：７頂点からなる木をすべて描け。
答は 11 個ある。７つの頂点の次数を多い順に列挙して表現すると...
[2, 2, 2, 2, 2, 1, 1] 型の木が１個，
[3, 2, 2, 2, 1, 1, 1] 型の木が３個，
[4, 2, 2, 1, 1, 1, 1] 型の木が２個，
[5, 2, 1, 1, 1, 1, 1] 型の木が１個，
[6, 1, 1, 1, 1, 1, 1] 型の木が１個，
[3, 3, 2, 1, 1, 1, 1] 型の木が２個，
[4, 3, 1, 1, 1, 1, 1] 型の木が１個
ということになる。