# Definition(s) Adjacent vertices have different colours! > [!NOTE] Definition (Vertex colouring) > Let $G$ be a [[Graphs|graph]] whose set of vertices is given by $V$. A $k$-colouring of $G$ is a [[Function|map]] $f:V\to C$ where for all $c\in C$, the [[Preimage (of set under a function)|preimage]] $f^{-1}(c)$ is [[Independent set of vertices (in graphs)|independent]] (i.e. its elements are pairwise adjacent in the complement of $G$) and $C$ is any finite set of cardinality $k$ called the colour set. Note $G$ is called [[Graph Colouring|k-partite]] is such a colouring exists. > [!Example] Example > Contents # Properties(s) # Application(s) **More examples**: # Reference(s) # Definition(s) > [!NOTE] Definiton (Bipartite Graph) > A [[Graphs|graph]] $G=(V,E)$ is *bipartite* iff $V$ admits a [[Partition of a Set|partition]] into $r$ classes such that every edge has it ends in different classes. > A k-partite graph is one that admits a k-[[Graph Colouring|colouring]]. # Properties > [!NOTE] Proposition (Odd cycles) > A graph is bipartite iff it contains no odd [[Cycle (Type of Simple Graph)|cycle]]. >*Proof*. > [!NOTE] Theorem (Hall, Marriage Theorem) > A *bipartite graph* $G$ with bipartition $\{ A,B \}$ contains a [[Matching (in graphs)|matching]] of $A$ iff $|N(S)| \geq |S| \quad \text{for all } S \subseteq A.$ >See [[Hall's Theorem|proof]].