โ† Discrete Mathematics learning path
Discrete Mathematics ยท Module 8 of 10

Graph theory basics

Vertices, edges, degrees and paths.

๐Ÿ“– Key ideas

  1. A graph G = (V, E) has vertices and edges; edges may be directed or undirected, weighted or not.
  2. Handshaking lemma: the sum of all degrees is twice the number of edges.
  3. Paths, cycles and connectivity describe how vertices are linked.
  4. Euler path uses every edge once (exists when 0 or 2 vertices have odd degree); Hamiltonian path visits every vertex once.
  5. Representations: adjacency matrix and adjacency list.
๐Ÿ’ก Real-life example: A graph is like a road map: towns are vertices and roads are edges.
DegreeNumber of edges at a vertex
Handshaking lemmaSum of degrees = 2 x edges
Euler circuitClosed walk using every edge once
Hamiltonian cycleCycle visiting every vertex once