Graph Theory Basics

Vertices and edges

A graph consists of a set of vertices, also called nodes, and a set of edges, each joining a pair of vertices. That is the entire definition. Vertices stand for the objects you care about, and edges stand for a relationship between two of them, such as a friendship or a road. Because a graph is fixed only by which pairs are joined, it can be drawn many ways; only the connections matter, not where the dots sit.

Two counts describe scale: the order of a graph is its number of vertices and the size is its number of edges. In an undirected graph an edge is an unordered pair, so a road runs both ways; in a directed graph, or digraph, each edge is an ordered pair with a source and a target, like a one-way street. Vertices joined by an edge are adjacent, and that edge is incident to both endpoints.

• Vertices represent objects; edges represent relationships between pairs of them.
• Order is the vertex count; size is the edge count.
• Undirected edges are unordered pairs; directed edges have a source and a target.
• Adjacent vertices share an edge, which is incident to both endpoints.

Degree and the handshaking lemma

The degree of a vertex is the number of edges incident to it, which in a simple graph is just its number of neighbours. If you add the degrees of every vertex, each edge is counted exactly twice, once at each endpoint. This gives the handshaking lemma: the sum of all degrees equals twice the number of edges, and so is always even.

A memorable consequence is that every graph has an even number of vertices of odd degree, because those odd degrees must pair up to keep the total even. The name comes from a party: the total number of hands shaken is even, so the number of people who shook an odd number of hands is even. In a directed graph the idea splits into in-degree and out-degree, whose sums are equal, each counting the edges.

• Degree is the number of edges incident to a vertex.
• Handshaking lemma: the degrees sum to twice the edge count, hence an even total.
• So a graph always has an even number of odd-degree vertices.
• Directed graphs split degree into in-degree and out-degree.

Walks, paths, and cycles

To move through a graph you follow edges. A walk is any sequence of vertices in which consecutive ones are joined by an edge, and it may repeat vertices and edges freely. A path is a walk that never repeats a vertex, the natural notion of a direct route between two vertices. The length of a walk or path is the number of edges it uses, not the number of vertices, a distinction worth keeping straight.

A cycle is a closed path: it returns to its starting vertex and repeats no vertex except the shared first and last. In a simple undirected graph the shortest possible cycle uses three edges, since walking out along an edge and straight back does not count as a cycle. Cycles matter in practice, since a cycle in a dependency graph is a circular dependency that can never be resolved. A graph with no cycles is called acyclic, and a directed acyclic graph is exactly one whose vertices admit a topological ordering, which is how build systems and schedulers decide what to run first.

Connectivity

An undirected graph is connected when there is a path between every pair of vertices, so you can travel from any node to any other without leaving the graph. When it is not connected the graph breaks into connected components, the maximal pieces within which travel is possible; two vertices share a component exactly when some path joins them.

Connectivity also has a robustness side. A vertex whose removal increases the number of components is a cut vertex, and an edge with the same effect is a bridge; these are the single points of failure in a network. For directed graphs the notion sharpens into strong connectivity: you can travel from any vertex to any other while respecting edge directions, stricter than being connected once directions are ignored.

Trees: the tidiest graphs

A tree is a connected graph with no cycles, and this modest definition forces a lot of structure. In a tree there is exactly one path between any two vertices, never zero and never two, which is why trees model hierarchies and unique routes so well. A tree on n vertices always has exactly n minus one edges, the fewest that can keep n vertices connected: remove any edge and it splits in two, add any edge and you create a cycle.

Rooted trees, where one vertex is singled out as the root, are everywhere in computing: file systems, the document object model in a browser, and the parse tree of a program, with the familiar language of parents, children, and leaves. A set of disjoint trees is a forest, and a spanning tree reaches every vertex of a larger graph.

Representing graphs in code

To compute with a graph you must store it, and two representations dominate. An adjacency list keeps, for each vertex, a list of its neighbours; it is compact for sparse graphs and makes scanning a vertex's connections fast. An adjacency matrix uses a grid whose entry for a row and column records whether an edge joins those two vertices, answering is there an edge in constant time at the cost of space quadratic in the vertex count.

With a representation chosen, the classic traversals bring graphs to life. Breadth-first search explores outward in rings and finds shortest paths counted in edges, while depth-first search dives along each branch before backtracking and exposes cycles and components. These traversals underpin routing, scheduling, and dependency resolution, and anchor the algorithmic toolkit you build later.