Graph
A graph is a discrete structure made up of vertices connected by edges. Graphs represent how groups of things are related. Based on whether that relation is symmetric, a graph may be directed or undirected.
Precisely, a graph \(G = (V, E)\) pairs up a set of vertices \(V\) with a set of edges \(E.\) It is possible for \(E\) to be empty.
The two vertices that participate in an edge are each other's neighbors. A vertex is adjacent to all its neighbors.
In a directed graph, or digraph, \(E\) is a subset of \(V \times V\), so each edge is an ordered pair of vertices \((a, b)\) depicted as an arrow pointing from \(a\) to \(b.\) The in-degree of a vertex is the number of edges pointing into it, and the out-degree of a vertex is the number of edges pointing out of it.
In an undirected graph, \(E\) is a set of size-\(2\) subsets of \(V\), so each edge is an unordered pair of vertices \(\set{a, b}\) depicted as a line connecting \(a\) and \(b.\) The degree of a vertex is the number of edges that are connected, or rather, incident to it.
Unlike graphs, multigraphs are defined as having a multiset of edges, which means multiple edges can exist between the same two vertices. Edges that exist between the same two vertices are called parallel edges.
A self-loop is any edge that connects a vertex back to itself. A directed self-loop takes the form \((v, v)\) for some \(v \in V\), and contributes exactly \(1\) to both the in-degree and out-degree of a vertex. An undirected self-loop looks like \(\set{v, v}\) instead, and contributes exactly \(2\) to the degree of a vertex.
Parallel edges and self-loops tend to complicate the definition of a graph and the degree of a vertex. Graphs that allow both of them are called pseudographs, which are basically multigraphs that can have self-loops. Graphs that do not have them are called simple graphs, or simply, "graphs."
Due to their versatility, graphs are essential to the design of algorithms that solve a diverse range of problems. These problems include: making a conflict-free schedule, stopping the spread of a contagious disease, modelling the internet, finding the quickest way to travel to a destination, and many more.
Degree-sum formula
In any undirected graph, the total degree is equal to twice the number of edges. This is because each edge contributes \(2\) to the total degree of the graph:
Graph induction
Proofs by induction involving graphs are quite different from the induction you might be used to, as it is based on the number of vertices or edges. Here's a carefully-written example of a proof by induction involving graphs:
Proof by induction: Let's perform induction on the number of edges, \(|E|.\)
Base case: First, we'll start with a graph \(G\) that has \(|V| \geq 0\) and \(|E| = 0.\) This is a graph that has an arbitrary number of vertices, but no edges at all. Since there are no edges, there can be no edges incident to any vertex, so all vertices have degree \(0.\) The sum all of those degrees, the total degree, is also \(0\): $$\text{totaldegree}(G) = 2|E|$$ $$(0) = 2(0)$$ $$0 = 0 \checkmark$$ Inductive step: Assume \(\text{totaldegree}(G) = 2|E|\) for any undirected graph \(G = (V, E)\) such that \(|V| \geq 0\) and \(|E| = k\), for some integer \(k \geq 0.\) Consider a graph \(G\) that has \(|V| \geq 0\) and exactly \(|E| = k+1\) edges, placed in any arrangement. Removing one of the edges (doesn't matter which edge) creates a new subgraph, \(G' = (V', E')\), where \(|E'| = k.\) Since \(G'\) has \(k\) edges, the inductive hypothesis applies to \(G'\): $$\text{totaldegree}(G') = 2|E'|$$ By the definition of an edge, the edge that was removed to create \(G'\) was once incident to \(2\) vertices, which means it contributed \(1\) to each of their degrees, adding up to a contribution of \(2\) to \(\text{totaldegree}(G).\) Its removal therefore decreased the total degree by \(2\): $$\text{totaldegree}(G') = \text{totaldegree}(G) - 2$$ Also, since \(G'\) has exactly \(1\) fewer edge than \(G\): $$|E'| = |E| - 1$$ Substituting: $$\text{totaldegree}(G') = 2|E'|$$ $$(\text{totaldegree}(G) - 2) = 2(|E| - 1)$$ $$\text{totaldegree}(G) - 2 = 2|E| - 2$$ $$\text{totaldegree}(G) = 2|E|$$ Thus, it can be concluded that if \(\text{totaldegree}(G) = 2|E|\) for any undirected graph \(G = (V, E)\) such that \(|V| \geq 0\) and \(|E| = k\), for some integer \(k \geq 0\), then \(\text{totaldegree}(G) = 2|E|\) for any undirected graph \(G = (V, E)\) such that \(|V| \geq 0\) and \(|E| = k+1.\) By the principle of mathematical induction, \(\text{totaldegree}(G) = 2|E|\) for any undirected graph \(G = (V, E)\) such that \(|V| \geq 0\) and \(|E| \geq 0.\) \(■\)
Connectivity
The connectivity of a graph is a measure of its resistance to becoming a disconnected graph. There are \(2\) ways to describe the connectivity of a graph.
Vertex-connectivity
The vertex connectivity \(\kappa(G)\) is the largest \(k\) such that the graph is \(k\)-vertex-connected.
Complete graphs have a vertex connectivity equal to \(1\) less than its number of vertices. It is a rule that \(\kappa(K_n) = n - 1.\) This is the highest possible vertex connectivity. So, complete graphs are the most resistant to disconnection, as its vertices have to be whittled down until there is a single, isolated vertex, which counts as a component.
To check that a graph is \(k\)-vertex-connected, you need to exhaustively check that the removal of any \((k-1)\)-size subset of its vertices keeps it connected. From combinatorics, we know that there are exactly \(\binom{n}{k-1}\) subsets to check to prove that a graph with \(n\) vertices is \(k\)-vertex-connected.
Edge-connectivity
The edge connectivity \(\lambda(G)\) is the largest \(k\) such that the graph is \(k\)-edge-connected.
Checking that a graph is \(k\)-edge-connected is also very exhausting. With \(m\) edges, you'll have to check that the removal of any of the \(\binom{m}{k-1}\) subsets of \(k-1\) edges will not cause the graph to become disconnected. Advanced algorithms, like the Ford-Fulkerson algorithm, can be adapted to efficiently determine the edge connectivity of a graph. For now, though, stick to checking the edge connectivity of graphs with not too many edges.
There's another rule for complete graphs. It's always true that \(\lambda(K_n) = n-1.\)