Vertices and Edges

Graph Theory · Axiom Academy

Understanding the fundamental building blocks of graph theory 1. Formal Definition of a Graph A graph is a mathematical structure consisting of two sets: a set of vertices and a set of edges that connect pairs of vertices. V is a non-empty set of vertices (also called nodes) E is a set of edges, where each edge connects two vertices Vertices (singular: vertex) are the fundamental units in a graph. They represent objects, entities, or points of interest. Vertices can represent anything: cities in a road network, people in a social network, computers in an internet topology, or states in a problem space. Edges represent relationships or connections between pairs of vertices. An edge between vertices u and v is often written as u, v or (u, v). Two vertices connected by an edge are called adjacent or neighbors . 4. Simple Graphs vs Multigraphs A simple graph has at most one edge between any pair of vertices and no loops (edges from a vertex to itself). A multigraph allows multiple edges between the same pair of vertices, representing multiple types of connections or repeated relationships. A loop is an edge that connects a vertex to itself. Loops are written as v, v or simply as (v). Simple graphs do not allow loops, but they appear in more general graph structures called pseudographs . 6. Directed vs Undirected Edges In an undirected graph , edges have no direction. The edge u, v is the same as v, u .

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