Graph Theory
Teachers KAMIDE, Norihiro Year 2　2nd semest [Department of Information and Electronic Engineering, Faculty of Science and Engineering] Special Subjects Elective　2credit 3C222

#### Course Description

In this course, basic graph theory in computer science is explained. The contents of the lectures are summarized as follows: (1) types of graphs (connected graph, planar graph, directed graph, network, etc.), (2) properties of graphs (connectivity, cyclicity, planarity, colorability, etc.), and (3) basic theorems in graph theory (Kuratowski's theorem, four color theorem, max-flow min-cut theorem, Menger's theorem, etc.).

#### Course Objectives

The aim of this course is to understand the following items: (1) basic concepts of graphs, (2) types of graphs, (3) properties of graphs and (4) basic theorems in graph theory.

Students are evaluated by a term examination, some midterm examinations, and some quizzes.

#### Textbook and Reference

KindTitleAuthorPublisher
TextbookNo textbook. The original slides and video contents are used.
ReferencesNo reference. The original slides and video contents are used.

#### Requirements(Assignments)

The slides of the lecture should be read. The video contents of the lecture should be viewed.

#### Note

LMS is used in this course.

#### Schedule

1Introduction: Outline of graph theory and its applications.
2Basic concepts of graph: Definitions of technical terms in graph theory.
3Connected graph (1): Eulerian graph. Euler's theorem.
4Connected graph (2): Hamiltonian graph. Ore's theorem. Dirac's theorem.
5Tree: Spanning tree. Cayley's theorem.
6Planar graph (1): Kuratowski's theorem. Euler's formula.
7Planar graph (2): Dual graph. Graph on curved surfaces.
8Infinite graph: Konig's lemma. Midterm examination.
9Coloring Problem (1): Vertex coloring. Face coloring. Four color theorem.
10Coloring Problem (2): Edge coloring. Chromatic polynomial.
11Directed graph (1): Strong orientation. Eulerian orientation.
12Directed graph (2): Network. Flow. Max-flow min-cut theorem.
13Hall's theorem: Bipartite graph. Hall's marriage theorem.
14Menger's theorem: Menger's theorem. Relation to other theorems.
15Advanced topics: Computational geometry. Term examination.