9. M2-Graph Theory

Master of Physics CY University

Introduction to Graph Theory


C Oguey ( oguey @ u-cergy.fr )     CM 18h, TD 12h

The classic branch of graph theory has seen a revolution in the last decades stimulated by the emergence of internet, social networks, world-wide trading and analogous multi-scale phenomena. The goal of the course is double: 1. provide an introduction to Graph Theory as a beautiful interdisciplinary science in itself; 2. give a background to study the active field of complex systems.


  1. Fundamentals
  2. Paths, cycles and trees
  3. Hamilton cycles & Euler circuits
  4. Planar graphs
  5. Electrical networks
  6. Vector spaces & matrices associated with graphs
  7. Flows, connectivity, matching
  8. Random graphs, generating functions



Based on projects (writen report + oral presentation) and/or final exam. Assessment to be defined.


Problem    set 1,    set 2


Write a concise but clear report, at most 8 pages. There will also be an oral presentation.

  Date dueSubject

Project 1tba Individual

Oral tba

Exam tba

Subjects for studies

  1. Colouring [B ch 5]
  2. Groups: Cayley, Schreier diagrams [B ch 8]
  3. Adjacency matrix and Laplacian [B ch 8, N 6.13]
  4. Random walks [B ch 9, N 6.14]
  5. Knots and links [B ch 10]
  6. Centrality, ranking, closeness, cliques, k-plexes, k-cores [N 7.1-7.8]
  7. Transitivity, clustering, reciprocity, similarity, homophily, mixing [N 7.9-7.13]
  8. Percolation [B ch 6, N ch 16]

Other subjects are welcome. Make proposals to lecturer.

C. Oguey, Nov. 2016