Information Package / Course Catalogue
Introduction to Graph Theory
Course Code: CSE115
Course Type: Required
Couse Group: First Cycle (Bachelor's Degree)
Education Language: English
Work Placement: N/A
Theory: 2
Prt.: 0
Credit: 2
Lab: 0
ECTS: 3
Objectives of the Course

Let the student gain an overview over the basics questions of graph theory. The focus is on understanding the structure of graphs and the techniques used to analyze problems in graph theory.

Course Content

Fundamental concepts of graphs and digraphs, trees, matchings, factorizations, connectivity, networks, graph colorings, planar graphs, and eulerian and hamiltonian graphs

Name of Lecturer(s)
Prof. İnci ERHAN
Learning Outcomes
1.Define a mathematical graph, identifying edges and vertices.
2.Represent real-life situations with mathematical graphs.
3.Understand how apply techniques of graph theory to solve applied problems.
4. To be able to define tree structures
5.To be able to construct graphical structures related to various problems
Recommended or Required Reading
1.West, Douglas Brent. Introduction to graph theory. Vol. 2. Upper Saddle River: Prentice hall, 2001.
2.Glenn Brookshear, Dennis Brylow, “Computer Science: An Overview” 12th Edition, Pearson, 2015
3.Lecture notes
Weekly Detailed Course Contents
Week 1 - Theoretical
Basic definitions, isomorphisms, walks, cycles and bipartite graphs
Week 2 - Theoretical
Basic definitions, isomorphisms, walks, cycles and bipartite graphs
Week 3 - Theoretical
Components, cut-edges, Eulerian graphs, vertex degrees and degree sequences, and directed graphs
Week 4 - Theoretical
Eulerian digraphs, trees and distance
Week 5 - Theoretical
Counting spanning trees and the matrix tree theorem, minimal spanning trees and shortest paths
Week 6 - Theoretical
Counting spanning trees and the matrix tree theorem, minimal spanning trees and shortest paths
Week 7 - Theoretical
Matchings, Hall's theorem and coverings, maximum matchings, factors
Week 8 - Theoretical
Matchings, Hall's theorem and coverings, maximum matchings, factors
Week 9 - Theoretical
Cuts and connectivity
Week 10 - Theoretical
Network flow problems, max-flow min-cut theorem
Week 11 - Theoretical
Vertex colorings, bounds on chromatic numbers and Mycielski's construction
Week 12 - Theoretical
Chromatic polynomials, chordal graphs, planar graphs
Week 13 - Theoretical
Euler's formula and Kuratowski's theorem
Week 14 - Theoretical
Five and four color theorems
Assessment Methods and Criteria
Type of AssessmentCountPercent
Midterm Examination1%30
Final Examination1%60
Quiz4%10
Workload Calculation
ActivitiesCountPreparationTimeTotal Work Load (hours)
Lecture - Theory140228
Quiz44018
Midterm Examination111213
Final Examination114216
TOTAL WORKLOAD (hours)75
Contribution of Learning Outcomes to Programme Outcomes
PÇ-1
PÇ-2
PÇ-3
PÇ-4
PÇ-5
PÇ-6
PÇ-7
PÇ-8
PÇ-9
PÇ-10
PÇ-11
OÇ-1
5
OÇ-2
5
4
4
3
3
OÇ-3
4
5
3
OÇ-4
4
3
5
3
3
OÇ-5
4
3
4
Adnan Menderes University - Information Package / Course Catalogue
2026