171.6 Bipartite graphs1.6 Bipartite graphsLet r ≥ 2 be an integer. A graph G = (V.E) is called r-partite ifr-partiteV admits a partition into r classes such that every edge has its endsin different classes: vertices in the same partition class must not beadjacent. Instead of ‘2-partite' one usually says bipartite.bipartiteK2.2.2=K3Fig. 1.6.1. Two 3-partite graphsAn r-partite graph in which every two vertices from different parcompletetition classes are adjacent is called complete; the complete r-partiter-partitegraphs for all r together are the complete multipartite graphs.Thecomplete r-partite graph Kni *..* Kn, is denoted by Kn...n,; ifKn.nr- ng =: s, we abbreviate this to K,. Thus, K, is the completen1=.KTr-partite graph in which every partition class contains exactly s ver-tices.6 (Figure 1.6.1 shows the example of the octahedron K3; compareits drawing with that in Figure 1.4.3.) Graphs of the form K1,n arecalled stars; the vertex in the singleton partition class of this Ki.n is thestarstar's centre.centre·Fig. 1.6.2. Three drawings of the bipartite graph K3,3 = K?Clearly, a bipartitegraph cannot contain an odd cycle,a cycle ofoddodd cyclelength. In fact, the bipartite graphs are characterized by this property:[8.2]Proposition 1.6.1. A graph is bipartite if and only if it contains noodd cycle.6Note that we obtain a Ky if we replace each vertex of a Kr by an independentS-set; our notation of K, is intended to hint at this connection.1.6 Bipartite graphs 17 1.6 Bipartite graphs Let r 2 be an integer. A graph G = (V,E) is called r-partite if r-partite V admits a partition into r classes such that every edge has its ends in different classes: vertices in the same partition class must not be adjacent. Instead of ‘2-partite’ one usually says bipartite. bipartite K2,2,2 = K3 2 Fig. 1.6.1. Two 3-partite graphs An r-partite graph in which every two vertices from different par￾tition classes are adjacent is called complete; the complete r-partite complete r-partite graphs for all r together are the complete multipartite graphs. The complete r-partite graph Kn1 ∗ ... ∗ Knr is denoted by Kn1,...,nr ; if Kn1,...,nr n1 = ... = nr =: s, we abbreviate this to Kr s . Thus, Kr s is the complete Kr s r-partite graph in which every partition class contains exactly s ver￾tices.6 (Figure 1.6.1 shows the example of the octahedron K3 2 ; compare its drawing with that in Figure 1.4.3.) Graphs of the form K1,n are called stars; the vertex in the singleton partition class of this K1,n is the star star’s centre. centre = = Fig. 1.6.2. Three drawings of the bipartite graph K3,3 = K2 3 Clearly, a bipartite graph cannot contain an odd cycle, a cycle of odd odd cycle length. In fact, the bipartite graphs are characterized by this property: Proposition 1.6.1. A graph is bipartite if and only if it contains no [ 5.3.1 ] [ 6.4.2 ] odd cycle. 6 Note that we obtain a Kr s if we replace each vertex of a Kr by an independent s-set; our notation of Kr s is intended to hint at this connection.