Graph Theory with Applications

3-connected 3-regular adjacency matrix algorithm assigned chromatic number chromatic polynomial clearly Combinatorial Theory complete graph connected graph corollary critical graph degree sequence denote diconnected digraph directed cycle directed path disjoint edge of G Erdös Euler tour exercise f-unsaturated follows G contains G is simple graph G graph of figure graph theory Hamilton cycle Hamilton path hamiltonian incidence matrix independent set induction integers k-colouring k-critical k-edge colouring labelling least lemma loopless Lovász Math maximal independent set maximum flow minimum cut minimum number nonhamiltonian nonplanar number of edges number of vertices obtained odd cycle P₁ perfect matching Petersen graph planar embedding planar graph plane problem Proof Let G Ramsey numbers shown in figure simple graph spanning subgraph spanning tree subgraph of G subset theorem tournament Tutte v₁ v₂ val f vertex set vertices of attachment vertices of G X₁ y)-paths Y₁