  Graph theory provides fundamental concepts for many fields of science like
statistical physics, network analysis and theoretical computer science. Here we
give a pedagogical introduction to graph theory, divided into three sections.
In the first, we introduce some basic notations and graph theoretical problems,
e.g. Eulerian circuits, vertex covers, and graph colorings. The second section
describes some fundamental algorithmic concepts to solve basic graph problems
numerically, as, e.g., depth-first search, calculation of strongly connected
components, and minimum-spanning tree algorithms. The last section introduces
random graphs and probabilistic tools to analyze the emergence of a giant
component and a giant q-core in these graphs.
  The presented text is published as the third chapter of the book "Phase
Transitions in Combinatorial Optimization Problem" (Wiley-VCH 2005). Together
with introductions to algorithms, to complexity theory and to basic statistical
mechanics over random structures, it provides the technical basis for the more
advanced chapters. These cover the analysis of phase transitions in
combinatorial optimization problems, algorithmic and analytical approaches
based on statistical physics tools (replica and cavity methods), the analysis
of various search algorithms and the development of efficient heuristic
algorithms, based on message passing techniques (warning, belief, and survey
propagation).
