Syllabus query

Academic Year/course: 2017/18

453 - Degree in Mathematics

27005 - Graphs and Combinatorics

Syllabus Information

Academic Year:
27005 - Graphs and Combinatorics
Faculty / School:
100 - Facultad de Ciencias
453 - Degree in Mathematics
Second semester
Subject Type:

1.1. Introduction


In the Mathematics degree of University of Zaragoza, "Graphs and Combinatorics" is a compulsory subject taught in the first year. It is included in the module Discrete Mathematics and Optimization, and is devoted essentially to the study of discrete structures. The two main topics of the subject are Combinatorics and Graph Theory. Special emphasis is placed on problem solving.

4.1. Assessment tasks (description of tasks, marking system and assessment criteria)


For regular students two options:


a)     - Homework (Completion of four problem sets)  --- 20%  of the score.

        - Final exam                                                     --- 80%  of the score.


b)     Only final exam (100%)


For non-regular students only option b).

5.1. Methodological overview


This course covers elementary discrete mathematics. It emphasizes mathematical definitions and proofs as well as applicable methods
The course consists of lectures and solving problem classes on the topics:  "permutations and combinations", "counting principles",  "recurrences", "generating functions", "elementary graph theory", "shortest path problems" and "optimal flow problems".


Four problem sets will be assigned during the course. Material covered in exercises will be tested on exams.



5.2. Learning tasks



The course consists of  lectures ( 2 sessions / week, 1 hour / session, 30 sessions) and solving problem classes (2 sessions / week, 1 hour / session, 30 sessions).



There are 4 problem sets. Typically, a problem set is due two week after it is assigned. By solving the problem sets a student can get 20% of the final score.


There are 4 additionals sessions  devoted to solving questions related with the homework. For these additional sesssions the students are splitted into small groups.


The students  can attend office hours and send questions to him/her teacher via email.


Additional information on the subject (calendar, timetable, problem sets, lecture notes,...)  appears in the web page of the subject (in University of Zaragoza ADD,



5.3. Syllabus

Program of the subject:


Part I

1.- Enumerative Combinatorics: Permutations and Combinations.

2.- Binomial coefficients and binomial formula.

3.- Recurrence relations. Some applications.

4.- The inclusion-exclusion principle. Applications.


Part II

5.- Generating Functions.

6.- Rational Generating Functions.


Part III

7.- Graphs: Definitions and notation.  

8.- Traversing a Graph. Algorithms  BFS and DFS.

9.- Applications of Graph Traversal: Connected components, strong components, bases.

10.-The number of trees and paths of a graph.


Part IV

11.- Weighted Graphs. Algorithms for the minimum spanning tree problem.

12.- The shortest path problem. Dijkstra’s algorithm.

13.- PERT-CPM algorithms for scheduling a set of project activities.


Part V

14.- Maximum flow in a network.

15.- The Ford- Fulkerson method for calculating a maximum flow.

16.- Menger’s theorems on connectivity of graphs.

17.- Maximum matching in bipartite graphs. Hall’s theorem.

18.- Some NP-Hard problems on graphs.


5.5. Bibliography and recommended resources



Lecture notes of the subject at


Complementary books:

Bóna, Miklós. A walk through combinatorics : an introduction to enumeration and graph theory / Miklos Bona . - 2nd ed.. Hackensack: World Scientific, 2008

Brualdi, Richard A. : Introductory combinatorics / Richard A. Brualdi . - 5th ed. Upper Saddle River, New Jersey : Pearson Prentice Hall, cop. 2010

Gross, Jonathan L.. Graph theory and its applications / Jonathan Gross, Jay Yellen . - 2nd ed. Boca Raton : Chapman & Hall/CRC, 2006

Lint, Jacobus Hendricus Van. A course in combinatorics / J. H. van Lint and R. M. Wilson . - [1st Ed., 2nd. repr.] Cambridge : Cambridge University Press, 1996

Pemmaraju, Sriram. Computational discrete mathematics : combinatorics and graph theory with mathematica / Sriram Pemmaraju, Steven Skiena . 1st publ., repr. Cambridge : Cambridge University Press, 2009

Stanley, Richard P.. Enumerative combinatorics / Richard P. Stanley . Cambridge ; New York : Cambridge University Press, cop. 1997-1999