1 GraphsA set V, together with a set E of two-element subsets of V, defines a simplegraph (V,E), where the ends of an edge uu are precisely the vertices u and v.Indeed, in any simple graph we may dispense with the incidence function b byming each edge as the unordered pair of its ends. In a diagram of such aenangraph, the labels of the edges may then be omitted.SPECIAL FAMILIES OF GRAPHSCertain types of graphs play prominent roles in graph theory. A complete graphis a simple graph in which any two vertices are adjacent, an empty graph one inwhich no two vertices are adjacent (that is, one whose edge set is empty). A graphis bipartite if its vertex set can be partitioned into two subsets X and Y so thatevery edge has one end in X and one end in Y:such a partition (X,Y) is calleda bipartition of the graph, and X and Y its parts.We denote a bipartite graphG with bipartition (X,Y) by G[X, Y]. If G[X, Y] is simple and every vertex in Xis joined to everrtexinY.thG is called acomplete bipartite graph. A staris a complete bipartite graph G[X,Y] with [X] = 1 or [Y] = 1. Figure 1.2 showsdiagrams of a completegraph,a complete bipartitegraph, and a star.50(a)(6)(c)Fig. 1.2. (a) A complete graph, (b) a complete bipartite graph, and (c) a starA path is a simple graph whose vertices can be arranged in a linear sequence insuch a way that two vertices are adjacent if they are consecutive in the sequenceand are nonadjacent otherwise. Likewise, a cycle on three or more vertices is asimple graph whose vertices can be arranged in a cyclic sequenceinsuchawaythattwoare adjacent if they are consecin the sequence. and ar311nonadjacent otherwise; a cycle on one vertex consists of a single vertex with aloop, and a cycle on two vertices consists of two vertices joined by a pair of paralleledges. The length of a path or a cycle is the number of its edges. A path or cycleof length k is called a k-path or k-cycle, respectively; the path or cycle is odd oreven according to the parity of k.A 3-cycle is often called a triangle, a 4-cyclea quadrilateral, a 5-cycle a pentagon, a 6-cycle a heragon, and so on. Figure 1.3depicts a 3-path and a 5-cycle4 1 Graphs A set V , together with a set E of two-element subsets of V , defines a simple graph (V,E), where the ends of an edge uv are precisely the vertices u and v. Indeed, in any simple graph we may dispense with the incidence function ψ by renaming each edge as the unordered pair of its ends. In a diagram of such a graph, the labels of the edges may then be omitted. Special Families of Graphs Certain types of graphs play prominent roles in graph theory. A complete graph is a simple graph in which any two vertices are adjacent, an empty graph one in which no two vertices are adjacent (that is, one whose edge set is empty). A graph is bipartite if its vertex set can be partitioned into two subsets X and Y so that every edge has one end in X and one end in Y ; such a partition (X,Y ) is called a bipartition of the graph, and X and Y its parts. We denote a bipartite graph G with bipartition (X,Y ) by G[X,Y ]. If G[X,Y ] is simple and every vertex in X is joined to every vertex in Y , then G is called a complete bipartite graph. A star is a complete bipartite graph G[X,Y ] with |X| = 1 or |Y | = 1. Figure 1.2 shows diagrams of a complete graph, a complete bipartite graph, and a star. v1 v2 v4 v3 v5 x1 x1 x2 x3 y1 y1 y2 y2 y3 y4 y3 y5 (a) (b) (c) Fig. 1.2. (a) A complete graph, (b) a complete bipartite graph, and (c) a star A path is a simple graph whose vertices can be arranged in a linear sequence in such a way that two vertices are adjacent if they are consecutive in the sequence, and are nonadjacent otherwise. Likewise, a cycle on three or more vertices is a simple graph whose vertices can be arranged in a cyclic sequence in such a way that two vertices are adjacent if they are consecutive in the sequence, and are nonadjacent otherwise; a cycle on one vertex consists of a single vertex with a loop, and a cycle on two vertices consists of two vertices joined by a pair of parallel edges. The length of a path or a cycle is the number of its edges. A path or cycle of length k is called a k-path or k-cycle, respectively; the path or cycle is odd or even according to the parity of k. A 3-cycle is often called a triangle, a 4-cycle a quadrilateral, a 5-cycle a pentagon, a 6-cycle a hexagon, and so on. Figure 1.3 depicts a 3-path and a 5-cycle