Graph Theory
TeachersKAMIDE, NorihiroStaffInfo
Grade, SemesterYear 2 2nd semest [Department of Information and Electronic Engineering, Faculty of Science and Engineering]
CategorySpecial Subjects
Elective, CreditsElective 2credit
 Syllabus Number3C222

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.

Grading Policy

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

Textbook and Reference

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


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


 LMS is used in this course.


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.