Graph Theory Fundamentals

• Graph (G): A pair (V, E) where V is a set of vertices and E is a set of edges connecting pairs of vertices.
• Types of Graphs:
  • Simple Graph: No loops or multiple edges.
  • Multigraph: Multiple edges allowed.
  • Directed Graph (Digraph): Edges have directions.
  • Weighted Graph: Edges have weights.

Understanding Subgraphs

• Subgraph: A graph H is a subgraph of G if V(H) ⊆ V(G) and E(H) ⊆ E(G).
• Induced Subgraph: Formed by a subset of vertices and all edges between them in G.

Fundamental Graph Properties

• Order: Number of vertices (|V|).
• Size: Number of edges (|E|).
• Degree: Number of edges incident to a vertex.

Common Graph Examples

• Complete Graph (K_n): Every pair of vertices is connected.
• Cycle Graph (C_n): Forms a closed loop.
• Path Graph (P_n): A sequence of vertices connected by edges in a line.
• Star Graph: One central vertex connected to all others.
• Wheel Graph (W_n): A cycle with one additional central vertex connected to all others.

Walks, Paths, Trails, and Circuits

• Walk: A sequence of vertices and edges.
• Path: A walk with no repeated vertices.
• Circuit: A walk that starts and ends at the same vertex.
• Trail: A walk with no repeated edges.

Connected and Disconnected Graphs

• Connected Graph: There's a path between every pair of vertices.
• Disconnected Graph: At least one pair of vertices has no path.

Graph Components

• Component: A maximal connected subgraph. Every disconnected graph is made of multiple components.

Eulerian Graphs and Trails

• Euler Trail: A trail using every edge exactly once.
• Euler Circuit: An Euler trail that starts and ends at the same vertex.
• Euler Graph: Has an Euler circuit, implying all vertices have an even degree.

Common Graph Operations

• Union (G ∪ H): Combines vertices and edges of both graphs.
• Intersection (G ∩ H): Common vertices and edges.
• Complement: Edges not present in the original graph.
• Cartesian Product: Vertices are pairs; edges follow rules from both graphs.

Hamiltonian Paths and Circuits

• Hamiltonian Path: Visits every vertex exactly once.
• Hamiltonian Circuit: A Hamiltonian path that returns to the starting vertex.
• Note: Not all Hamiltonian graphs are Eulerian, and vice versa.

Traveling Salesman Problem (TSP) Explained

• Problem: Find the shortest possible circuit visiting each city (vertex) exactly once and returning to the start.
• Type: NP-hard.
• Relation: It is a weighted Hamiltonian circuit problem.
• Solution Approaches: Brute force, dynamic programming, approximation algorithms.