Introduction to Graph Theory

Math for CS · Axiom Academy

Vertices, edges, and the language of connections We write |V| = n for the number of vertices and |E| = m for the number of edges. These two numbers determine the size of the graph and the complexity of most graph algorithms. Undirected vs. Directed Graphs An edge has no direction — it connects u and v symmetrically. If you can go from u to v , you can go from v to u . An edge (u, v) is an ordered pair — it goes from u to v . The edge (u, v) is different from (v, u) . Each edge carries a numerical weight w(e) , representing cost, distance, capacity, or some other quantity. Both directed and undirected graphs can be weighted. Every edge contributes 2 to the total degree count (one for each endpoint). This simple identity has powerful consequences — for example, the number of odd-degree vertices must be even. Two vertices u and v are adjacent (or neighbors) if there is an edge between them. The neighborhood of v , written N(v) , is the set of all vertices adjacent to v . The length of a path or walk is the number of edges it uses. In a weighted graph, the length is usually the sum of edge weights. is a walk (not a path, since B repeats) An undirected graph is connected if there exists a path between every pair of vertices. If not, the graph breaks into connected components — maximal connected subgraphs. For directed graphs, we distinguish: Strongly connected: There is a directed path from u to v and from v to u for all pairs

This is the written version of the interactive lesson above. See the full Math for CS course.