# Graph Theory Topics

## 1. Types and Graphs and Basic Definitions

- Graphs and Subgraphs
- Adjacency and Incidence
- Neighbourhood, Degrees and Degree Sequence
- The Maximum and Minimum Degrees of a Graph
- Isolated Vertices, Leaves, and Pendant Edges
- Realizability of Graphs
- Graph Isomorphisms
- Walks, Trails, Paths, Cycles, and Circuits
- Graph Bridges
- Components of a Graph
- The Handshaking Lemma
- Regular Graphs
- Complete Graphs
- Cycle Graphs
- The Circumference and Girth of a Graph
- Null Graphs
- Platonic Graphs
- Bipartite and Complete Bipartite Graphs
- Tree Graphs
- Path Graphs
- Cube Graphs
- Complement Graphs
- Self Complementary Graphs
- The Instant Insanity Problem

## 2. Eulerian and Hamiltonian Graphs

- Eulerian Graphs and Semi-Eulerian Graphs
- Euler's Theorem
- Hamiltonian Graphs and Semi-Hamiltonian Graphs
- Dirac's and Ore's Theorem
- Knight's Tour Problem
- Gray Codes
- Digraphs
- Subdigraphs and Underlying Graphs
- Disconnected, Connected, and Strongly Connected Digraphs
- Orientable Graphs
- Out-Degree Sequence and In-Degree Sequence
- The Handshaking Dilemma
- Eulerian Digraphs
- Hamiltonian Digraphs
- The Rotating Drum Problem
- Tournaments and Rankings
- Tournament Kings
- Adjacency Matrices
- Incidence Matrices

## 3. Tree Graphs

## 4. Vertex and Edge Cutsets and Euler's Formula

- Vertex and Edge Cutsets
- Relation of Min Vertex Cutsets, Min Edge Cutsets, The Minimum Degree, and Maximum Degree
- Euler's Formula
- Planar Graphs and Plane Drawings
- Proof of the Existence of only 5 Platonic Solids
- Conditions for Planarity
- Algebraic Proof of the Existence of only 5 Platonic Solids
- Subdivisions and Contractions
- Kuratowski's Theorem
- Graph Duality

## 5. Vertex and Edge Colourings

### References

**1.**Aldous, Joan M., Wilson, Robin J., "*Graphs and Applications: An Introductory Approach*".

Submit an Error: Do you think that you see an error in any of the pages? Click the link and let us know so that we can fix it as soon as possible! All help is greatly appreciated with there being so many possibilities that can be overlooked. |