MA010 Graph Theory

Faculty of Informatics
Autumn 2025
Extent and Intensity
2/1/0. 3 credit(s) (plus extra credits for completion). Type of Completion: zk (examination).
In-person direct teaching
Teacher(s)
prof. RNDr. Petr Hliněný, Ph.D. (lecturer)
Mgr. Jan Jedelský (seminar tutor)
Guaranteed by
prof. RNDr. Petr Hliněný, Ph.D.
Department of Computer Science – Faculty of Informatics
Supplier department: Department of Computer Science – Faculty of Informatics
Timetable
Mon 15. 9. to Mon 15. 12. Mon 8:00–9:50 B204
  • Timetable of Seminar Groups:
MA010/01: Thu 18. 9. to Thu 11. 12. each even Thursday 12:00–13:50 C416, J. Jedelský
MA010/02: Thu 25. 9. to Thu 18. 12. each odd Thursday 12:00–13:50 C416, J. Jedelský
Prerequisites
! PřF:M5140 Graph Theory &&!NOW( PřF:M5140 Graph Theory )
Discrete mathematics. IB000 (or equivalent from other schools) is strongly recommended.
Course Enrolment Limitations
The course is also offered to the students of the fields other than those the course is directly associated with.
The capacity limit for the course is 50 student(s).
Current registration and enrolment status: enrolled: 32/50, only registered: 0/50, only registered with preference (fields directly associated with the programme): 0/50
fields of study / plans the course is directly associated with
there are 22 fields of study the course is directly associated with, display
Course objectives
This is a standard introductory course in graph theory, assuming no prior knowledge of graphs. The course aims to present basic graph theory concepts and statements with a particular focus on those relevant in algorithms and computer science in general. Selected advanced graph theory topics will also be covered. Although the content of this course is primarily targeted at computer science students, it should be accessible to all students with sufficient background in discrete mathematics.
Learning outcomes
At the end of the course, students shall understand basic concenpts in graph theory; be able to reproduce the proofs of some fundamental statements in graph theory; be able to solve unseen simple graph theory problems; and be ready to apply their knowledge particularly in computer science.
Syllabus
  • Basic graph theory notions: graphs, subgraph, graph isomorphism, vertex degree, paths, cycles, connected components, directed graphs.
  • Trees, Hamilton cycles, Dirac’s and Ore’s conditions.
  • Planar graphs, duality of planar graphs, Euler's formula and its applications.
  • Graph coloring, Five Color Theorem, Brooks’ Theorem, Vizing’s Theorem.
  • Interval graphs, chordal graphs, and their chromatic properties.
  • Vertex and edge connectivity.
  • Matchings in graphs, Hall’s Theorem.
  • Ramsey's Theorem.
  • Selected advanced topics (to be chosen from): Graph minors, graph embeddings on surfaces, planarity testing, list coloring, Tutte’s Theorem, Cayley’s formula.
  • Expect these points to be adjusted and reordered during the semester.
Literature
    recommended literature
  • DIESTEL, Reinhard. Graph theory. 4th ed. Heidelberg: Springer, 2010, xviii, 436. ISBN 9783642142789. info
  • http://diestel-graph-theory.com/
  • MATOUŠEK, Jiří and Jaroslav NEŠETŘIL. Kapitoly z diskrétní matematiky. 3., upr. a dopl. vyd. V Praze: Karolinum, 2007, 423 s. ISBN 9788024614113. info
  • HLINĚNÝ, Petr. Základy teorie grafů. Elportál. Brno: Masarykova univerzita, 2010. ISSN 1802-128X. URL info
Teaching methods
MA010 is taught in weekly 2-hour lectures, which are primarily focused on introducing the material (concepts, statements, proofs). The lectures are complemented with bi-weekly 2-hour tutorials where examples and problems related to the material presented during the lectures are made available to practice.
Assessment methods
Students are expected to understand (not only memorize) the concepts taught in the lectures, including simple mathematical proofs. The resulting grade will based on the semester test (25%) and the final written exam (75%) - both parts require meeting their respective minimal thresholds. Grades B and A moreover require a subsequent oral discussion on the exam topics and questions.
Language of instruction
English
Follow-Up Courses
Further comments (probably available only in Czech)
Study Materials
The course is taught annually.
Listed among pre-requisites of other courses
Teacher's information
Basic information regarding course curriculum and examination can be found in the online syllabus MA010 in the Information System - "https://is.muni.cz/auth/el/1433/podzim20**/MA010/index.qwarp".
The course is also listed under the following terms Autumn 2002, Autumn 2003, Autumn 2004, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.
  • Enrolment Statistics (recent)
  • Permalink: https://is.muni.cz/course/fi/autumn2025/MA010