Outline

• What is a graph
  vertices (sometimes "nodes") and edges, vertex degrees,
  simple graphs, cycles, paths, complete graphs, bipartite graphs
• Subgraphs and isomorphism
  subgraph and induced subgraph, cycles (triangles), paths and cliques in a graph;
  isomorphism between two graphs, how to recognize (non-)isomorphic graphs
• Trees and forests
  graphs without cycles, basic properties of trees
• Digraphs and Multigraphs
  directed graphs (with arrows), multigraphs (with multiple edges and loops)
• ~optional~ Appendix
  degree sequence of a graph, tree isomorphism algorithm

Goals

This is a basic introduction which shows what is a graph and what are the few basic terms needed to understand and describe a graph (its vertices and edges, subgraphs, and isomorphism with other graphs). Most importantly, students should now be able to work with graphs as familiar objects and to understand the important role of isomorphism in graph theory (i.e., when two graphs are "essentially the same").

Graphs versus Multigraphs

It is not a big deal, but all students should understand from the beginning that there exist graphs which we mean simple (edges are two-element subsets, hence no bunches of parallel edges and no loops are possible), and then there are multigraphs in which a bunch of edges may share the same pair of endvertices (parallel edges) and even an edge with both ends in the same vertex may exist (called a loop). When we say a graph, we mean simple graph! 

Pictures of graphs

When dealing with graphs (on a paper, not in a computer), the best way to "get grip" on it is to draw a nice graph picture. One of the early goals of our course is to teach you to draw graphs nicely, and see their properties in the pictures. Often, one has to try several pictures of the same graph before (s)he finds the right one - the one on which the answer or solution appears obvious. Likewise the next example (how many nonisomorphic graphs can you see?)...

Try playing yourself with graph pictures, either with a pencil and paper, or with modern computer tools such as in the Planarity game and with the yEd (java) or Grapher (android) visual graph editors.

Study materials

Course book  [Invitation to Discrete Mathematics (by Jiří Matoušek, Jaroslav Nešetřil)]

Study Section 4.1, starting parts of 4.2 and 4.3, and Section 5.1.

Remarks
In the basic graph terminology, there is one really annoying ambiguity -- with the notation P_n for a path, some authors mean the index n to be the number of vertices, not the length (number of edges). We stick with both the course books and thus "P_n" is the path of length n. As for another common ambiguity, regarding the notation for indegrees and outdegrees of directed graphs, MA010 lectures use "d-" for indegree and "d+" for outdegree (opposite to this book) since this seems to be more frequent.

Older editions of this book (both English and Czech) lack one of the starting chapters, and so the graph theory chapters start with number 3, not 4 as referred above. Intelligent students can surely subtract 1 from the chapter number in such a case... Furthermore, some of the book sections, mainly concerning Eulerian graphs and shortest paths, are arranged differently in the older or Czech editions. All our references are based on the 2008 English edition (see on google books).

Advanced course book  [Graph theory (by Reinhard Diestel)]

Study Sections 1.1-1.3 and 1.5-1.6 (very short sections), voluntarily also 1.10

However, before starting to read [Diestel], we advise the students to get familiar with graphs using other, less advanced resources.

External online resources

About interactive tutorials

Whenever possible, we complement the theoretical content of the lectures with online available tutorials and demonstrations. These are provided as external links and you are encouraged to try them. Again, some notations of these external tutorials may conflict with our lectures, and then (let us know) we will explain the differences before the link.

IS Questionnaires

Besides tutorials, all students have a good chance to test their routine graph-theory skills in these online IS MU questionnaires below. The questionnaires are provided only for the first few basic lectures (since, obviously, more difficult math theory cannot be seriously tested online).

Simple glossary

Finally, we provide a link to a brief glossary of graph theory notation (wikipedia). Use it only for a quick reference, but not for studying! Some parts may differ from the lectures, and then the lectured stuff takes precedence (such as for P_n; let us know if this happens elsewhere).