Graph Theory Concepts and Applications

Connected Graphs and Cycles

  • Connected Graph: A graph where there is a path between every pair of vertices.
  • Cycles: Closed paths in a graph.

Problems and Induction Proofs

  • Starred problems are not required to be written up.
  • Some problems may require significant time to solve.

Special Circuits in Graphs

  • Considered special circuits in graphs like Eulerian circuits.

The Königsberg Bridge Problem

  • Originates from the problem in Königsberg (now Kaliningrad) involving land masses (Northern and Southern) and bridges.
  • The problem asks whether it is possible to start at one land mass, cross each bridge exactly once, and return to the starting point.
  • Euler represented each land mass as a vertex and each bridge as a line segment, creating a multigraph.
  • In the Königsberg graph, the degrees of the vertices were 3, 3, 3, and 5.

Eulerian Circuits

  • An Eulerian circuit starts at a vertex, traverses each edge exactly once, and returns to the starting vertex.
  • The Königsberg bridge problem has no Eulerian circuit because not all vertices have even degrees.

Theorem for Eulerian Graphs

  • A graph G is Eulerian if and only if every vertex of G has an even degree.

    • G is Eulerian \iff every vertex of G has an even degree

  • Proof (One Direction):

    • If G has an Eulerian circuit, then every vertex has an even degree.
    • Each visit to a vertex involves entering and leaving, thus contributing two to the degree.

  • The other direction (if every vertex has even degree, then an Eulerian circuit exists) was proven by Hierholzer about a hundred years later.

Hamiltonian Cycles

  • A Hamiltonian cycle is a cycle that visits every vertex exactly once.
  • A graph with a Hamiltonian cycle is called Hamiltonian.

Comparison of Eulerian and Hamiltonian Paths

  • Eulerian: Traverses each edge exactly once.
  • Hamiltonian: Visits each vertex exactly once.
  • Detecting whether a graph is Eulerian has a quick algorithm (verifying connectivity and even degrees).
  • Finding a Hamiltonian cycle in a large graph is a difficult problem with no known quick algorithm.

Chest Graph

  • Vertices arranged in a grid (e.g., 16x16).
  • Represents a chessboard with moves possible by a king and a knight.

King's Moves

  • Orthogonally (horizontally/vertically) to an adjacent square.
  • Diagonally to an adjacent square.

Knight's Moves

  • L-shaped: two steps in one direction (orthogonally) and one step perpendicularly.

Subgraphs and Examples

  • A subgraph is a graph formed using edges from a larger graph.

  • Examples include subgraphs with Hamiltonian cycles shaped like letters (H, E, T).

  • A Hamiltonian cycle shaped like "H."

  • An Eulerian circuit shaped like "E" (all vertices have even degree).

  • Eulerian circuit: Start at a vertex and traverse each edge exactly once, returning to the start.

Trees

  • A tree is a connected graph with no cycles.

  • Can be drawn with a root, trunk, branches, and leaves.

Artwork Examples

  • Hamiltonian cycle portraits (William Rowan Hamilton, Linda Hamilton, Alexander Hamilton).

  • Eulerian circuit designs.

Traversable Eulerian Trail

  • An open-ended Eulerian trail that can be easily traversed by always going straight.

Spanning Trees

*Given a graph, a spanning tree is a tree that includes all the vertices of the graph, using only the existing edges from the original graph.

  • If there are n vertices, the number of spanning trees is n^{n-2}. For example, if n = 7, then the number of spanning trees is 7^{7-2} = 7^5.

  • Spanning tree portrait of Arthur Cayley.

Practical Applications - "Psychopath" Puzzle

  • Drawing lines without lifting a finger.
  • Based on Eulerian trails.
  • Puzzle can be solved if started at a vertex with an odd degree.

Conclusion

  • Connection of graph theory to various artistic and practical applications.