1GraphsContents1.1 Graphs and TheRepresentation.................ANDEXAMPLES42DEBAE4SPECIALFAMILIESOFGRAPHS67INCIDENCEANDADJACENCYMATRICESVERTEX DEGREES1828PROOFTWOWAYS1.215and Automorphisms......oorons....EODTSAUTOMORPHISNABELLEDGRAPHS1.3GraphingfromOtherStructures....POLY+..INCIDENCE GRAPIINTERSECTIONGRAPHS1.4Constructing Graphs from Other Graphs .JNIONANDSCTION:RSA11.5Directed Graphs1.611Related Reading.SHISTORY OF GRAPH THEORY.1.1 Graphs and Their RepresentationDEFINITIONS AND EXAMPLESMany real-world situations can conveniently be described by means of a diagranconsistingof asetof pointstogetherwithlines joiningcertainpairs ofthesepoints1 Graphs Contents 1.1 Graphs and Their Representation . ................. 1 Definitions and Examples ............................ 1 Drawings of Graphs ................................. 2 Special Families of Graphs .......................... 4 Incidence and Adjacency Matrices .................. 6 Vertex Degrees ..................................... 7 Proof Technique: Counting in Two Ways ............ 8 1.2 Isomorphisms and Automorphisms . . . . . . . . . . . . . . . . . 12 Isomorphisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Testing for Isomorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 Automorphisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 Labelled Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.3 Graphs Arising from Other Structures . . . . . . . . . . . . . 20 Polyhedral Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 Set Systems and Hypergraphs . . . . . . . . . . . . . . . . . . . . . . . 21 Incidence Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 Intersection Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.4 Constructing Graphs from Other Graphs . . . . . . . . . . . 29 Union and Intersection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 Cartesian Product . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 1.5 Directed Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 1.6 Infinite Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 1.7 Related Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 History of Graph Theory. . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 1.1 Graphs and Their Representation Definitions and Examples Many real-world situations can conveniently be described by means of a diagram consisting of a set of points together with lines joining certain pairs of these points