Introduction to Graphs Summary

Graph Theory · Axiom Academy

SUMMARY Introduction to Graphs Let's review the foundational concepts of graph theory and how graphs model relationships and connections in mathematics and the real world. Definition: A graph G = (V, E) consists of a set of vertices V and a set of edges E Models relationships: Graphs abstract real-world connections into a mathematical structure Focus on structure: Physical details are stripped away, leaving only the essential pattern of connections Universal tool: Same framework applies to social networks, computer networks, molecules, road maps, and countless other systems Vertices (nodes): Represent objects, entities, or points of interest in the system Edges (links): Represent relationships or connections between pairs of vertices Adjacent vertices: Two vertices are adjacent if connected by an edge Incident edge: An edge is incident to a vertex if the vertex is an endpoint of that edge Order and size: |V| is the order (number of vertices); |E| is the size (number of edges) Definition: The degree of a vertex is the number of edges incident to it Notation: deg(v) denotes the degree of vertex v Handshaking Lemma: The sum of all vertex degrees equals twice the number of edges: Σ deg(v) = 2|E| Odd-degree pairs: Every graph has an even number of odd-degree vertices (a consequence of the Handshaking Lemma) Complete graph K n : Every vertex is connected to every other vertex; has n(n-1)/2 edges Path P n : Vertices arranged in a line with n-1 edges connecting consecutive vertices

This is the written version of the interactive lesson above. See the full Graph Theory course.