A First Course in Graph Theory and Combinatorics

Inhaltsverzeichnis

1. Frontmatter

2. Chapter 1. Basic Graph Theory

   Sebastian M. Cioabă, M. Ram Murty

   Abstract

   Graph theory may be said to have begun with the 1736 paper by the Swiss mathematician Leonhard Euler (1707–1783) devoted to the Königsberg bridges problem. In the town of Königsberg (now Kaliningrad in western Russia), there were four land masses and seven bridges connecting them as shown in Fig. 1.1. The challenge was to leave home and to traverse each bridge exactly once and return home.

3. Chapter 2. Basic Counting

   Sebastian M. Cioabă, M. Ram Murty

   Abstract

   The earliest historical record of combinatorial questions seems to be the Chandaḥ sūtra of Piṅgala in the third century BCE, India (Plofker 2009). There, we find extensive discussion about all the possible arrangements of poetic meters. There is even a discussion of the binary system. What is now called the Pascal triangle seems to have been known to the ancient Arabs, Indians, and the Chinese, several centuries before Pascal (Joseph 1991). However, modern combinatorics begins with a classic work of the French mathematician Abraham de Moivre (1667–1754) in the 17th century.

4. Chapter 3. The Principle of Inclusion and Exclusion

   Sebastian M. Cioabă, M. Ram Murty

   Abstract

   The principle of inclusion and exclusion was used by the French mathematician Abraham de Moivre (1667–1754) in 1718 to calculate the number of derangements on n elements.

5. Chapter 4. Graphs and Matrices

   Sebastian M. Cioaba, M. Ram Murty

   Abstract

   Given a graph, one can associate various matrices to encode its information. The adjacency matrix A of a graph \(X=(V,E)\) is the matrix whose rows and columns are indexed by the vertices of X, where A(x, y) equals the number of edges between x and y.

6. Chapter 5. Trees

   Sebastian M. Cioaba, M. Ram Murty

   Abstract

   A forest is an acyclic graph, that is, a graph with no cycles. The connected components of a forest are called trees. Therefore, a tree is a connected graph that contains no cycles.

7. Chapter 6. Möbius Inversion and Graph Colouring

   Sebastian M. Cioabă, M. Ram Murty

   Abstract

   August Ferdinand Möbius (1790–1868) was a German mathematician and astronomer who introduced the function which bears his name in 1831 and proved the well-known inversion formula.

8. Chapter 7. Enumeration Under Group Action

   Sebastian M. Cioabă, M. Ram Murty

   Abstract

   A group \((G,*)\) consists of a set G together with a binary operation \(*\) on G satisfying the following axioms.

9. Chapter 8. Matching Theory

   Sebastian M. Cioabă, M. Ram Murty

   Abstract

   A matching of a graph \(X=(V,E)\) is a collection of edges of X which are pairwise disjoint. The vertices incident to the edges of a matching M are saturated by M. A perfect matching is a matching that saturates all the vertices of X. Obviously, a necessary condition for that to happen is that X has an even number of vertices, but that is not sufficient in general.

10. Chapter 9. Block Designs

    Sebastian M. Cioabă, M. Ram Murty

    Abstract

    Let V be a n-dimensional vector space over the finite field \(\mathbb {F}_q\) of q elements. Our first result determines the number \(\begin{bmatrix}{n}\\ {k}\end{bmatrix}_{q}\) of k-dimensional vector subspaces of V.

11. Chapter 10. Planar Graphs

    Sebastian M. Cioabă, M. Ram Murty

    Abstract

    A curve in the plane is the image of a continuous map from [0, 1] to \(\mathbb {R}^2\). A graph is said to be embedded in the plane if it can be drawn on the plane so that its vertices correspond to distinct points of the plane, its edges are represented by curves connecting their corresponding endpoints and no two edges/curves intersect except only at their endpoints.

12. Chapter 11. Edges and Cycles

    Sebastian M. Cioabă, M. Ram Murty

    Abstract

    In the previous chapters, we have been considering vertex colourings. Now we will consider edge colourings of a graph. We will say that two edges are incident if they have a common vertex. We would like to properly colour the edges, in the sense that no two incident edges receive the same colour.

13. Chapter 12. Expanders and Ramanujan Graphs

    Sebastian M. Cioabă, M. Ram Murty

    Abstract

    We summarize below some basic properties of the eigenvalues of regular graphs..

14. Chapter 13. Hints

    Sebastian M. Cioabă, M. Ram Murty

    Abstract

    Exercise 1.6.15 Start with an arbitrary bipartite subgraph with two non-empty partite sets. For each vertex x, if the number of neighbours of x which are contained in its colour class is greater than the number of neighbours of x which are contained in the other colour class, then move x to the other colour class.

15. 14. Correction to: Graphs and Matrices

    Sebastian M. Cioabă, M. Ram Murty

16. Backmatter