Graph Theory

1-factor 2-connected adjacency matrix automorphism Beineke bipartite block c₁ Chartrand chromatic number chromatic polynomial cocycle Combinatorial complete graphs components connected graph Corollary critical graph cubic graph cutpoint d₁ d₂ defined denoted digraph disconnected dual embedded enumeration exactly Four Color Conjecture G contains G is connected G₁ and G₂ genus given graph graph G graph theory graphical hamiltonian graph Harary homeomorphic incident induced subgraph integer isomorphic K₁ labeled graph Let G line graph line of G line-core line-disjoint line-symmetric Math matroid maximum number Menger's Theorem n-connected nonadjacent points nontrivial number of lines number of points obtained outerplanar graph P₁ pair partition paths joining permutation group planar graph plane map points and lines points of degree points of G Pólya's problem proof proved result rooted trees S₂ shown in Fig spanning path spanning tree subgraph of G tournament triangles Tutte u₁ uniquely n-colorable vertices w₁