THE JULIUS PETERSEN GRAPH THEORY CENTENNIAL
CONTENTS INTRODUCTION: PROBLEMS OF GRAPH THEORY PATH PROBLEMS COLORING PROBLEMS ISOMORPHIC GRAPHS PLANAR GRAPHS DISJOINT PATHS SHORTEST PATHS AND MORE A BASIC CONCEPTS EQUIVALENT GRAPHS MULTIGRAPHS DIRECTED GRAPHS AND MIXED GRAPHS COMPLETE GRAPHS CYCLE GRAPHS PATHS IN A GRAPH OPEN AND CLOSED PATHS; CYCLES SUBGRAPHS THE COMPLEMENT OF A GRAPH DEGREES OF VERTICES THE DEGREE SEQUENCE OF A GRAPH REGULAR GRAPHS CONNECTED AND DISCONNECTED GRAPHS COMPONENTS OF A GRAPH MORE PROBLEMS B ISOMORPHIC GRAPHS GRAPH THEORY C BIPARTITE GRAPHS COMPLETE BIPARTITE GRAPHS BIPARTITE GRAPHS AND MATRICES CYCLES IN A BIPARTITE GRAPH CYCLE THEOREM FOR BIPARTITE GRAPHS PROOF OF THE CYCLE THEOREM D TREES AND FORESTS PRUNING A TREE DIRECTED TREES SPANNING TREES COUNTING SPANNING TREES CODEWORDS FOR TREES: PRUFER’S METHOD E SPANNING TREE ALGORITHMS CONSTRUCTING SPANNING TREES WEIGHTED GRAPHS MINIMAL SPANNING TREES PRIM’S ALGORITHM TABLES FOR PRIM’S ALGORITHM THE REDUCTION ALGORITHM SPANNING TREES AND SHORTEST PATHS MINIMAL PATHS IN A WEIGHTED GRAPH MINIMAL PATH ALGORITHM, ?RST ATTEMPT MINIMAL PATH ALGORITHM, REVISED TABLES FOR DIJKSTRA’S ALGORITHM MINIMAL PATHS IN A DIRECTED GRAPH NEGATIVE WEIGHTS F EULER PATHS THE K¨ONIGSBERG BRIDGE PROBLEM EULER PATHS IN DIRECTED GRAPHS AND DIRECTED MULTIGRAPHS APPLICATION OF EULER PATHS: STATE DIAGRAMS, DEBRUIJN SEQUENCES, AND ROTATING WHEELS G HAMILTON PATHS AND CYCLES SOME NEGATIVE TESTS POSITIVE TESTS FOR HAMILTON CYCLES SOME PROOFS H PLANAR GRAPHS REGIONS FORMED BY A PLANE DIAGRAM PROOF THAT K5 IS NON-PLANAR, USING EULER’S FORMULA CONTENTS NON-PLANAR GRAPHS AND KURATOWSKI’S THEOREM I INDEPENDENCE AND COVERING THE INDEPENDENCE NUMBERS OF A GRAPH A GRAPH GAME COVERING SETS AND COVERING NUMBERS J CONNECTIONS AND OBSTRUCTIONS INTERNALLY DISJOINT PATHS EDGE-DISJOINT PATHS PATH CONNECTION NUMBERS BLOCKING SETS K-CONNECTED GRAPHS VERTEX CUT SETS AND VERTEX CUT NUMBERS K VERTEX COLORING THE VERTEX COLORING NUMBER OF A GRAPH VERTEX COLORING THEOREMS MAP COLORING L EDGE COLORING THE EDGE COLORING NUMBER OF A GRAPH EDGE COLORING OF COMPLETE GRAPHS EDGE COLORING OF BIPARTITE GRAPHS EDGE COLOR SWITCH PROOF OF EDGE COLORING THEOREM #3 APPLICATION OF EDGE COLORING: THE SCHEDULING PROBLEM M MATCHING THEORY FOR BIPARTITE GRAPHS THE MAX/MIN PRINCIPLE PROOF OF THE K¨ONIG–EGERVARY THEOREM THE COLORED DIGRAPH CONSTRUCTION MATCHING EXTENSION ALGORITHM PROOF OF THE COLORED DIGRAPH THEOREM MATRIX INTERPRETATION OF THE K¨ONIG–EGERVARY THEOREM HALL’S THEOREM AND ITS CONSEQUENCES N APPLICATIONS OF MATCHING THEORY SETS AND REPRESENTATIVES LATIN SQUARES PERMUTATION MATRICES GRAPH THEORY THE OPTIMAL ASSIGNMENT PROBLEM O CYCLE-FREE DIGRAPHS CHAINS AND ANTICHAINS CHAIN DECOMPOSITIONS PROOF OF DILWORTH’S THEOREM P NETWORK FLOW THEORY FLOWS IN A NETWORK CUTS AND CAPACITIES Q FLOW PROBLEMS WITH LOWER BOUNDS THE SUPPLY AND DEMAND PROBLEM ANSWERS TO SELECTED PROBLEMS