グラフ理論（Graph theory）とは、グラフの持つ様々な性質を解明し、日常の様々な場面で利用することを目的とする数学分野の1つである。
グラフ理論におけるグラフ （Graph）とは、頂点(node)と辺(edge)により構成された図形のことである。グラフは主に、有向グラフ （directed graph）と無向グラフ （undirected graph）の2つに分類される。有向グラフとは、頂点と向きを持つ辺（矢印）により構成されたグラフであり、無向グラフとは、頂点と辺により構成されたグラフである。有向グラフの辺を有向辺、無向グラフの辺を無向辺という。また、ある2頂点が辺で結ばれている場合、その2頂点は隣接するという。この教科書では、特に利用分野の多い無向グラフについて説明する。そのため、この教科書では、無向グラフを単にグラフと記述することとする。
グラフは頂点の集合と辺の集合の2つの順序対で構成される。グラフGを構成する頂点の集合をV、辺の集合をEとし、G=(V,E)と表記する。頂点をuやvで表すことが多く、頂点u,vを結ぶ辺を\{u,v\}または、uvと表す。しかし、紛らわしい表記であるため、この教科書では、\{u,v\}と表記することとする。ただし、\{u,v\}と\{v,u\}はどちらでも構わない。
「グラフの定義」で説明したとおり、グラフは頂点と辺により構成される。とは言うものの、実際にどのように作図すればいいのかわからないだろう。この節では、グラフの作図について説明する。まず、頂点を丸で表し、辺を直線または、曲線で表す。そのとき、マルの大きさや直線の長さ、曲線の曲がり具合はグラフの本質には関係ないので、厳密に作図する必要はない。以下にグラフの作図例を紹介する。
ファイル:Wikibooks graph theory.png|作図例
頂点の周囲にuやvなどと記すと、グラフを表記するとき、便利である。頂点の中にラベル（重み）を記す場合があるが、まず、グラフの基本から説明する必要があるため、この節で紹介するのはやめておく。
(1)以下のグラフG_1をG_1=(V_1,E_1)の形式で表せ。
ファイル:Wikibooks graph theory2.png|G_1
V_1=\{v_1,v_2,v_3,v_4\}, E_1=\{\{v_1,v_3\},\{v_1,v_4\},\{v_2,v_3\},\{v_2,v_4\}\}であるから、
G_1=(\{v_1,v_2,v_3,v_4\},\{\{v_1,v_3\},\{v_1,v_4\},\{v_2,v_3\},\{v_2,v_4\}\})
(2)グラフG_2=(\{v_1,v_2,v_3,v_4\},\{\{v_1,v_2\},\{v_1,v_3\},\{v_1,v_4\},\{v_2,v_3\},\{v_3,v_4\}\})を作図せよ。
ファイル:Wikibooks graph theory3.png|G_2
(1)以下のグラフG_3をG_3=(V_3,E_3)の形式で表せ。
ファイル:Wikibooks graph theory4.png|G_3
(2)グラフG_4=(\{v_1,v_2,v_3,v_4,v_5\},\{\{v_1,v_3\},\{v_2,v_3\},\{v_2,v_5\},\{v_3,v_4\},\{v_3,v_5\},\{v_4,v_5\}\})を作図せよ。
頂点の数を位数（order）、辺の数をサイズという。
グラフにおける次数（degree）とは、ある頂点に結ばれている辺の数である。
あるグラフにおいて、\{v_0,v_1\},\{v_1,v_2\},\cdots,\{v_{n-1},v_n\}がすべて辺であるとき、それぞれの辺の集合を頂点v_0
と頂点v_nを結ぶ道(path)と言う。
ある2つのグラフが同型（isomorphism）であるということは、それぞれのグラフを構成する頂点と辺の結びつきが同じであるということである。
連結(connected)なグラフとは、任意の2頂点間に道が存在するグラフのことである。
完全グラフ（complete graph）とは、すべての頂点同士が辺で結ばれているグラフのことである。頂点数 n の完全グラフを K_n と表す。
オイラーグラフ：オイラー閉トレイルが存在するグラフをオイラーグラフと呼ぶ。
オイラー閉トレイル：グラフのすべての辺とすべての点を含む閉トレイルをオイラー閉トレイルと呼ぶ。
オイラートレイル：グラフのすべての辺とすべての点を含むトレイルをオイラートレイルと呼ぶ。
ハミルトングラフ：ハミルトン閉路を含むグラフをハミルトングラフと呼ぶ。
ハミルトン閉路：グラフのすべての頂点を含む閉路をハミルトン閉路と呼ぶ。
根（root）という頂点を持ち、
問題の解答を記載しておく。
(1)
G_3=(\{v_1,v_2,v_3,v_4,v_5\},\{\{v_1,v_3\},\{v_1,v_5\},\{v_2,v_3\},\{v_2,v_4\},\{v_2,v_5\},\{v_3,v_5\}\})
(2)
ファイル:Wikibooks graph theory5.png|G_4
以下のURLにアクセスするとファイルをダウンロードすることができる。もちろん、自由に利用して構わない。
https://skydrive.live.com/redir.aspx?cid=322baa2fe886dd76&resid=322BAA2FE886DD76!230&parid=root (リンク切れ)
この教科書に利用されているファイルWikibooks graph theory*.pngはgraph*.svgやgraph*.png,graph*.epsの3種類の形式で保存されている。そのため、様々な用途に利用できる。フォルダとして一括でダウンロードすることも可能である。