Graph Theory
This chapter contains an introduction to graph theory. The purpose of this chapter is not to give a purely theoretical introduction, so most concepts are shown with problems whose solution involves this idea. First, basic concepts are presented, and impor
- PDF / 360,401 Bytes
- 15 Pages / 477 x 684 pts Page_size
- 92 Downloads / 223 Views
Graph Theory
4.1
Basic Concepts
Graph theory is one of the most useful tools when solving combinatorics problems. It helps us reduce problems and handle concepts in a much simpler way. The main tricks and ideas were presented in the previous chapters. Even though our main purpose in this book is to solve olympiad problems, we need to emphasize that graph theory is a very large and beautiful field by itself. Graph theory is said to have started in 1736, with Euler. However, the first book on graph theory was published by König in the twentieth century (1936). Even though graph theory had an accelerated growth in that century, it is still possible find open problems1 that do not required a lot of theory to understand (and, in some cases, solve). This does not mean in any way that such problems are easy. A graph G is a pair (V , E), where V is a non-empty set and E is a multiset2 of unordered pairs of elements of V . The elements of V are called the vertices and the elements of E are called the edges of G. The reason why E is a multiset is to allow G to have an edge more than once; however, we will not deal with this kind of graphs. A subgraph G of G = (V , E) is a pair (V , E ), where V is a subset of V , E is a subset of E and (V , E ) is also a graph. Given a graph G, the set of vertices is usually denoted by v(G) and the (multi) set of edges is denoted by e(G).3 Each graph has a geometric representation. One places one point in the plane for each vertex, and a pair of points are joined with a line segment whenever the
1 An
open problem is one that has not been solved yet.
multiset is a set than can have the same element more than once, for example {1, 1, 2, 3} is a multiset. 2A 3 If
the set of vertices and the set of edges are empty, this still fits the definition of a graph, commonly referred to as the empty graph. It is a technical detail and can normally be ignored, but it is a good thing to keep in the back of our minds when strange inductions or proofs are needed. P. Soberón, Problem-Solving Methods in Combinatorics, DOI 10.1007/978-3-0348-0597-1_4, © Springer Basel 2013
43
44
4 Graph Theory
corresponding vertices form an edge. Sometimes in the geometric representation edges have a common point, this does not mean that there is a new vertex there.4
The figure shows a graph with vertices v1 , v2 , v3 , v4 , v5 and edges {v1 , v2 }, {v1 , v4 }, {v1 , v5 }, {v1 , v5 }, {v2 , v2 }. Given a graph G, we say G is simple if there are no edges of only one vertex and there are no multiple edges. From now on, all graphs are simple unless specified otherwise. The term multigraph usually refers to graphs that are not simple. Given a graph G and its vertex v0 , we say that an edge A is incident in v0 if v0 is one of its vertices. We also say that two vertices v0 and v1 are adjacent if they form an edge. We say that v0 has degree k if it is adjacent to exactly k vertices, and then we write d(v0 ) = k.
In the graph above d(A) = 2, d(B) = 3, d(C) = 2, d(D) = 1, d(E) = 0. Example 4.1.1 Let G be a gra
Data Loading...
