Math 428: Section 1.3 - Common Classes of Graphs PDF

Math 428 1.3: Common Classes of Graphs Definitions A graph G is called a path if its vertices can be (re)labeled u1, u2, , un so that its edges are u1u2, u2u3, , u n 1 un. A graph that is a path of order n is denoted by Pn. A graph G of order n 3 is called a cycle if its...

Math 428 1.3: Common Classes of Graphs Definitions A graph G is called a path if its vertices can be (re)labeled u1, u2, , un so that its edges are u1u2, u2u3, , u n 1 un. A graph that is a path of order n is denoted by Pn. A graph G of order n 3 is called a cycle if its vertices can be (re)labeled u1, u2, , un so that its edges are u1u2, u2u3, , u n 1 un , u n u1. A graph that is a cycle of order n is denoted by Cn. A graph G is called complete if every pair of distinct vertices is adjacent. A complete graph of order n is denoted by Kn. If G is a complete graph of order n, then its size is m is given by n nn 1 m. 2 2 ***There are many ways of drawing the same graph. The complement Ḡ of a graph G is the graph with vertex set V G such that for each pair of distinct vertices u, v of G, uv is an edge of Ḡ i↵ uv is not an edge of G. If graph G has order n and size m, then Ḡ has order still n but its size is n nn 1 mḠ C n, 2 m m m. 2 2 If G is a complete graph of order n (that is, G Kn), then K̄n has n vertices but zero edges and it is called the empty graph of order n. A graph G V, E is bipartite if the vertex set V can be partitioned into two sets A and B (the bipartition or partite sets) such that no edge in E has both endpoints in the same set of the bipartition. Example. Show that the graphs are bipartite by finding bipartitions. Theorem 1.12 A nontrivial graph G is bipartite if and only if G contains no odd cycles. Proof: 1. ( ) Assume that G is a bipartite graph with partite sets A and B. For the sake of contradiction, assume that G contains an odd cycle, say, u1 u2 u3 u2n 1u1.  2. ( ) Assume that G contains no odd cycle. Without loss of generality, we can assume that G is a connected, nontrivial graph. (Graphs that consist of bipatite components are bipartite.) Let u V G and define sets X and Y by X v V G d u.v odd and Y v V G d u.v even. Suppose, for the sake of contradiction, that G is not bipartite.  2. ( ) Assume that G contains no odd cycle. Without loss of generality, we can assume that G is a connected, nontrivial graph. (Graphs that consist of bipatite components are bipartite.) Let u V G and define sets X and Y by X v V G d u.v odd and Y v V G d u.v even. Suppose, for the sake of contradiction, that G is not bipartite. Then, there exists edge uv E G such that u, v are both in X or both in Y.  2. ( ) Assume that G contains no odd cycle. Without loss of generality, we can assume that G is a connected, nontrivial graph. (Graphs that consist of bipatite components are bipartite.) Let u V G and define sets X and Y by X v V G d u.v odd and Y v V G d u.v even. Suppose, for the sake of contradiction, that G is not bipartite. Then, there exists edge uv E G such that u, v are both in X or both in Y. Consider the cycle that results from combining a u v path of minimum length, followed by the edge vw, followed by a w u path of minimum length. This is a cycle of odd length (why?), which is a contradiction. Therefore, our original assumption (that G is not bipartite) was false. So, G is a bipartite graph. Definitions & Notation If G and H are graphs, then the join G H is the graph that consists of G H and all edges joining a vertex of G and a vertex of H.  If G and H are graphs, then the Cartesian Product G H is the graph with vertex set V G H V G V H. Two distinct vertices u, v and x, y are joined by an edge if either a) u x and vy E H , or b) v y and ux E G. How to Draw G H Replace each x E G by a copy of the graph H, call it Hx. Then, join corre- sponding vertices of Hx and Hy if x and y are adjacent in G. Otherwise, we do not add any edges between Hx and Hy. Problem. Draw the join and the Cartesian product of the two graphs. Theorem There is no graph of order n 2 whose vertices have all di↵erent degree. Proof: