MAT344H1 Lecture Notes - Lecture 3: If And Only If, Dual Graph, Pentagon
Document Summary
Cor: the number of odd degree vertices is even. Proof: if we have an odd number of odd numbers (eg 3, 5, 13), then their sum is also odd. First recall that for any graph g=(v, e) number of odd vertices, then. Def: a bipartite graph g = (v, e) is a graph whose vertex set v is the disjoint union of two subsets such that all edges of g connect a vertex of to a vertext of. Only if: suppose g contains an odd circuit, then without loss of generality (wlog) let . If: we construct a splitting as follows: pick any vertex v in (v, e). Theorem: a graph is bipartite iff it contains no circuits of odd length. Def: a graph g=(v, e) is planar if it can be drawn on the board without crossing any of its edges. To prove a graph g is not planar, try circle-chord method.
