数学の予備知識なしで読める、わかりやすい入門書です。参考図も豊富で、説明の飛躍もあまりなく読みやすい本です。北大の井上純一先生の講義(PDF)を参考にするとより分かりやすいので必見です。他にHPhttp://coolee.at.infoseek.co.jp/graphtheory.html#-1
http://topicmaps.u-gakugei.ac.jp/form/art&science/graph/graph.aspもきっと参考になります 。
他に古い本ですが「群とグラフ」グロスマン、マグナスと「現代数学の招待」日本評論社p.17〜46の遠山啓の解説はすばらしいので必見。