Outline

• Connections in a graph, components
  walks in a graph,the equivalence relation of connections between pairs of vertices, connected components
  
• Searching through a graph
  principles of depth-first search and breadth-first search algorithms
  
• Higher levels of connectivity
  k-connected and k-edge connected graphs, characterization of 2-connected graphs ("ear addition", or subdivisions of edges), Menger's theorem (see also Lecture 6)
  
• Eulerian tours and trails
  tours (closed) or trails (not closed) in a graph - no repetition of edges, Eulerian tours or trails, Eulerian graphs ("seven bridges") and the even degree condition
  

Goals

This lecture is primarily devoted to the basic task a computer scientist (or engineer) has to do with a graph: to algorithmically "search through the graph". Students will learn about the concept of graph connectivity and see a skeleton of the two basic graph search algorithms DFS a BFS. Additionally, the extended concepts of higher vertex- and edge-connectivity are briefly surveyed, and a specific theoretical attention is paid to 2-connected graphs. Lastly, students will hear about the famous "seven bridges" problem which is considered as the historical basis of the whole modern graph theory, and its solution given by Euler - his even-degree condition.

Course book  [Invitation to Discrete Mathematics (by Jiří Matoušek, Jaroslav Nešetřil)]:

Study Sections 4.2 (a fragment on pages 120-121), whole 4.4, and voluntarily also 4.5 and 4.6.

On the other hand, the (rather simple) algorithmic part - searching through a graph (DFS, BFS, etc...), is not primarily covered by the book, and we refer to some great online resources below.

Remark
Some other literature use terms "path", "circuit", or "cycle" in a context where repetition of vertices (not edges though) is allowed. This is WRONG, and we shall always use the correct terms "trail" or "(closed) tour" there.

Interactive tutorials

IS Questionaries