Introduction

edit

Although Graph Theory, and Combinatorics in general, has very few prerequisites, an introductory course must unfortunately start with many definitions. This lecture may therefore be a little dry, but it will provide the necessary backbone for the rest of the course.

What is a graph?

edit

A lot of situations from the real world can usefully be described by means of a diagram consisting of a set of points together with various lines joining certain pairs of these points. For example, if you are planning a wedding, the points could represent your guests, with the lines representing pairs of people who it would be bearable to have sitting together. Another example is the Kevin Bacon Graph, in which points represent Hollywood actors, and lines represent collaborations between actors. Yet another example is a computer network, in which the points could represent the computers and printers, with lines representing physical and wireless connections.

A graph is a mathematical abstration of the above. Formally, a graph   consists of a set of vertices  , and a set of edges  , where an edge   is a 2-element subset of  . A graph is usually represented by a picture, in which the vertices are represented by points, and the edges by lines or curves joining two elements.

Examples

edit

Let  , and let  . (The edges are usually written as   rather than   for ease of notation.) This can be depicted by the following picture:  

For another example, let  , and let  . This can be depicted by the following picture:

 
Second example of a graph

Isomorphism

edit

Given a particular graph, it can be depicted in countless ways, and there is usually no "best" way of depicting a graph. For example the second graph could also be depicted in the following way: . Note that this is still the same graph - the location of the vertices and edges in the diagram makes no difference to the graph.

This rearrangement of the vertices has shown a connection between our two graph examples. If we relabel the vertices of this new drawing in such a way that  ,  ,  ,   and  , we get the first diagram. In the vast majority of Graph Theory examples and results, the choice of labels for the vertices are pretty much irrelevant, and most graph theorists would see these two graphs as being the same. The relationship between these two graphs is an isomorphism, and they are said to be isomorphic.

Formally, an isomorphism from graph   to graph   is a mapping   which is one-to-one ( ) , onto (for all  , there exists   such that  ), and such that for any vertices  , the edge   is contained in   if and only if the edge   is contained in  . Graphs   and   are said to be isomorphic if there is an isomorphism from   to  . Unless specified, we will not distinguish between isomorphic graphs.

Note that it is by no means easy to tell if two graphs are isomorphic. See Problem 1 on the problem sheet for examples.

Necessary Definitions

edit

There are various terms relating to the vertices and edges of a graph which, although obvious, need to be defined. Given vertices   and edge   of graph  , edge   is said to join the vertices   and  , which are called the endvertices of the edge.   and   are neighbouring or adjacent vertices of  , and are incident with edge  .

The order of   is the number of vertices, whereas the size is the number of edges.

The Degree Sequence

edit

Given a vertex  , the degree of   (denoted by  ) is the number of edges incident with  . The smallest degree of the vertices of   is called the minimum degree of   and is denoted by  . The maximum degree is denoted by  .

In the examples above, each vertex has degree 2, so the minimum and maximum degree are 2. A graph in which every vertex is of degree   is called  -regular, and a graph is called regular if it is  -regular for some  .

We now have our first theorem of the course. It is the belief of many proponents of Combinatorics that the best way to teach it is through problems. To that end, the theorems are not provided with full proofs in the lectures, but instead with a roadmap with which the student can find the proof themselves. At the end of each theorem a link is provided to a proof page.

Theorem 1: The sum of the degrees of the vertices of a graph   is precisely twice the size of  .

Proof Roadmap: Let   incident with  . By considering how many elements of   each vertex   is part of, count the number of elements of  . Count the number of elements of   again, this time by considering how many elements each edge   is part of.

QED (Full Proof)

If the graph   has vertices  , then the degree sequence of   is the sequence  . For ease of notation, this sequence is often written in increasing order.

Common graphs

edit

In the same way that the alternating, cyclic, dihedral and symmetric groups occur so often that it is useful to have fixed notation for them, similarly there are various graphs which it is useful to be able to describe easily.

Empty Graphs

edit

The empty graph   has   and  . That is to say that is has   vertices and 0 edges. It is called the empty graph on   vertices.

Complete Graphs

edit

In contrast to the empty graph, the complete graph   has every edge. That is to say that   and  . It has   vertices and   edges. It is called the complete graph on   vertices.

Paths

edit

The path graph   has   and  . It has   vertices and   edges. It is called the path on   vertices or simply the n-path.

Cycles

edit

For  , the cycle graph   has   and  . It has   vertices and   edges It is called the cycle on   vertices or simply the n-cycle.

Subgraphs

edit

A question of common importance in Graph Theory is to tell, given a complicated graph  , whether we can, by removing various edges and vertices, show the presence of a certain other graph  . In this case   is said to be a subgraph of  . Formally, given graphs   with  ,   is a subgraph of   if  . The subgraph is said to be spanning if  , and induced if   consists of every edge of   with both vertices in  .

Cliques, Cycles and Paths

edit

There are a few examples of subgraphs which are particularly important. These correspond to the special graphs mentioned above. Examples in this section will be subgraphs of the Kevin Bacon graph mentioned above.

Cliques

edit

If subgraph   of   is isomorphic to a complete graph   for some  , then   is said to be a clique of  . Note that all cliques are induced subgraphs. A trivial example in the Kevin Bacon graph would be a subgraph H consisting of the entire cast of some film, with all edges present. Clique 1 is such an example with the film Who's Afraid of Virginia Woolf? (1966). Cliques can also arise in other ways. For example, in Clique 2 each edge corresponds to a different film.

The size of the largest clique in graph   is the clique number of  . The largest clique in the Kevin Bacon Graph probably consists of the largest cast of any film.

Independent Sets

edit

If induced subgraph   of   is isomorphic to an empty graph   for some  ,   is said to be an independent set of  . In other words, an independent set is a set of vertices between which no edges lie. For example, Angelina Jolie, Catherine Zeta-Jones, Drew Barrymore, Dennis Hopper, Eddie Murphy, Kevin Bacon, Kevin Spacey, Madonna, Mel Gibson and Shirley Maclaine form an independent set in the Kevin Bacon graph. The size of the largest independent set in graph   is the independence number of  . In the case of the Kevin Bacon graph this probably consists of a collection of extras who have each appeared in one movie, these movies being different.

Cycles

edit

If subgraph   is isomorphic to a cycle   for some  , then   is a cycle of  . Here is an example of a cycle in the Kevin Bacon Graph which is currently an induced subgraph.

The size of the smallest cycle in a graph   is the girth of  . The size of the largest cycle is the circumference of  . For the Kevin Bacon graph, the girth is 3, as Robert De Niro, Jodie Foster and Joe Pesci can attest. The circumference is a much harder question, but probably will consist of most of the vertices on the graph of degree at least 2.

Paths

edit

If subgraph   is isomorphic to a path   for some  , then   is a path of  . Here is an example of a path in the Kevin Bacon Graph which is currently an induced subgraph.

If the vertices at the end of the path are  , it is called a  -path. If there exists a path between   and  , the distance between   and   is the length (number of edges) of the shortest  -path. The diameter of a graph is the longest distance between two points. If, as is commonly suggested, every actor can be connected to Kevin Bacon with at most 6 links, the diameter must be at most 12.

r-partite Graphs

edit

A graph   is said to be bipartite with vertex classes   and   if the vertex set of   is the disjoint union of   and  , and each edge joins a vertex of   to a vertex of  . There is no edge joining two elements in   (or in  ). Similarly   is r-partite with vertex classes   iff the vertex set is the disjoint union of the  , and no edge goes between vertices in the same class.

Connected Components

edit

If graph   has the property that for each pair of vertices  , there is some  -path, then   is said to be connected. If   is not connected, then it breaks down uniquely into several connected subgraphs. A maximal connected induced subgraph of   is called a component.

A vertex whose deletion increases the number of components is called a cutvertex, whilst an edge with the same property is called a bridge.

Conclusion

edit

This lecture contained a necessary initial set of definitions and concepts, along with some examples to simplify understanding. Next time we will ground these by investigating properties of bipartite graphs, and of a particular kind of graph called a tree.

  Resource type: this resource contains a lecture or lecture notes.