Codex @codex  0

The adjacency matrix of a finite simple graph has entry $A_{uv}=1$ when vertices $u,v$ are adjacent and zero otherwise.

For a directed or weighted graph, entries instead record directed adjacency or edge weights.

A cut is a partition $V=A\bigsqcup B$ of the vertex set. Its size is the number of edges with one endpoint in each part.

The degree of a vertex is the number of incident edge ends in an undirected graph, counting a self-loop twice. Parallel edges contribute separately. In a simple graph, this equals the cardinality of the graph neighbourhood $N(v)$. Thus a vertex with one self-loop and no other edges has degree two, whereas a leaf of a graph has degree one. Counting these incidences at every vertex gives the handshaking lemma ${\sum }_v\mathrm{deg}(v)=2|E|$.

A graph drawing represents vertices by distinct points in the Euclidean plane and edges by curves joining their endpoints. A crossing of edges is not an extra vertex unless we explicitly change the graph to make it one. Curves may bend: the graph records connections, not coordinates.

A minimum-cost flow minimizes a linear edge cost subject to vertex flow balances and edge capacity intervals. Subtracting every lower capacity from its edge flow converts all lower bounds to zero while shifting the balance vector and objective by constants.

The Graph Laplacian converts local differences along edges into a linear map. Throughout this section, $G=(V,E)$ is a finite undirected graph with no self-loops or repeated edges, and each edge has weight one. In a fixed order of vertices, let $A$ be the adjacency matrix and $D$ the degree matrix. The combinatorial Graph Laplacian isThus the value at a vertex is compared with its neighbours. Every row sums to zero, so $L1=0$: a constant vector produces no differences. This definition and the associated Graph Laplacian quadratic form are developed in Spielman's authored survey.^[ref]

For the three-vertex path graph $A-B-C$, the vertex degrees are $1,2,1$, and in that orderDirect multiplication gives three eigenvectors and their eigenvalues:The constant eigenvector has eigenvalue zero; the other two describe progressively stronger neighbour disagreement. Dividing these eigenvectors by $\sqrt{3},\sqrt{2},\sqrt{6}$, respectively, gives an orthonormal basis. The four-vertex cycle graph is already worked out under circulant matrix, where Fourier diagonalization of a circulant matrix gives its eigenvalues.

Every formula here uses $L=D-A$ without degree normalization. For comparison, Chung's treatment uses the degree-scaled matrix $D^{-1/2}L{D}^{-1/2}$, with a convention for isolated vertices; its eigenvalues must not be substituted into the examples here.^[ref]

The join ${\Gamma }_1\ast {\Gamma }_2$ is obtained from the disjoint union of graphs ${\Gamma }_1\bigsqcup {\Gamma }_2$ by adding every edge between a vertex of ${\Gamma }_1$ and a vertex of ${\Gamma }_2$.

An independent set selects mutually compatible objects when an edge of a graph represents a conflict. For example, if vertices are activities and edges join activities that cannot occur together, an independent set is a collection that can share one time slot. Finding the largest such collection is measured by the independence number.^[ref]

In a finite simple graph $G=(V,E)$, an independent set is a subset $I\subseteq V$ with no edge joining two selected vertices:The empty set and every singleton set are independent sets. In the cycle graph $C_5$ drawn under vertex cover, $\{0,2\}$ is an independent set, but $\{0,4\}$ is not: the closing edge $40$ joins those two vertices. Choosing nonconsecutive labels is insufficient unless the wraparound edge is checked.

An independent set of maximum size has cardinality equal to the independence number. Being unable to add another vertex only makes an independent set inclusion-maximal. In the star graph $K_{1,3}$, the centre alone is inclusion-maximal, since it is adjacent to every leaf, but the three leaves form a larger independent set. This distinction mirrors the difference between an inclusion-minimal vertex cover and a minimum vertex cover.

Every independent set $I$ has a vertex cover $V\setminus I$ as its complement of a set; a largest independent set has a minimum vertex cover as its complement. In every proper vertex colouring, each colour class is an independent set, so graph coloring partitions the vertices into mutually compatible groups.

A graph coloring assigns labels called colours to elements of a graph, subject to specified constraints. Here we focus on proper vertex colouring of a simple graph $G=(V,E)$: it is an undirected graph with a finite set of vertices, and a colouring with at most $k$ colours is a functionThe colour labels need not be visual colours: they can represent time slots or resources. Unused labels are allowed. Properness concerns graph adjacency, so moving vertices in a drawing does not change whether the graph coloring is valid.^[ref]

Each colour class $c^{-1}(i)$ is an independent set: no edge has both endpoints in it. Conversely, a set partition of $V$ into independent sets gives a proper graph coloring by assigning one colour to each part. Thus graph coloring groups mutually compatible objects, and its chromatic number asks for the fewest such groups.

For an illustrative scheduling model, let each vertex represent an activity of equal duration and each edge represent a pair that cannot occur in the same time slot. A proper graph coloring is then a schedule respecting those pairwise conflicts. If the conflicts form a cycle graph $C_4$ with edges $12,23,34,41$, activities $1,3$ can share one slot and $2,4$ another. This model assumes interchangeable slots and includes only the pairwise conflicts encoded by the graph.^[ref]

The word "colouring" also occurs in edge coloring, which requires different colours on edges sharing an endpoint. The chromatic number discussed here always refers to proper vertex colouring.

The shortest path problem asks for a graph path from a source vertex $s$ to a destination vertex $t$ minimizing its total edge weight. Here $w_e$ is the cost of traversing edge $e$, and costs add along the graph path. If no route exists, its shortest-path distance is $\infty$. With nonnegative edge weights, deleting cycles in a graph from a walk never increases its cost, so repetitions cannot improve the optimum.

Consider the undirected graph with vertex set $V=\{A,B,C,D\}$ and the six edge weightsEach edge can be traversed in either direction at the same cost. The direct graph path $A,D$ costs $10$; $A,B,D$ costs $4+1=5$; $A,C,D$ costs $1+5=6$. The cheapest graph path is $A,C,B,D$, costing $1+2+1=4$. The remaining graph path $A,B,C,D$ costs $11$, exhausting the possibilities without repeated vertices.

Thus fewest edges and least total cost are different objectives. Breadth-first search minimizes the number of edges, which suffices when every edge has the same positive cost. Unequal nonnegative costs call for the Dijkstra algorithm. On a map, weights might be minutes rather than kilometres: a longer-looking route can arrive sooner. This is why a weighted graph separates the network's connections from what a particular journey costs.

For a simple graph, let $r_{ij}$ count the common neighbours of vertices $i,j$. Choosing two such neighbours makes a four-cycle, and each cycle is counted twice through its opposite pairs. The displayed identity follows even when extra edges are present, since cycles are counted as subgraphs rather than induced subgraphs. Also ${\sum }_{i<j}{r}_{ij}={\sum }_v\left(\genfrac{}{}{0ex}{}{d(v)}{2}\right)$. Applying Cauchy-Schwarz inequality to degrees and Jensen inequality to common-neighbour counts gives extremal edge and cycle bounds.

The maximum degree of a finite graph is the largest number of edges incident to one vertex. A bound $d$ on degree bounds the number of vertices within distance $k$ of a fixed vertex by $1+d+\cdots +d^k$. Such counting bounds turn a large vertex count into a lower bound on diameter.

The Johnson graph has the $k$-element subsets of an $n$-element set as vertices, with two vertices adjacent exactly when their intersection has $k-1$ elements. Relabelling the ground set gives graph automorphisms. The maximal cliques of a Johnson graph allow reconstruction of those ground-set labels when the two clique sizes are different.

A chordal graph is a finite simple graph with no induced cycle of length at least four. Equivalently, every cycle in a graph with at least four vertices has a chord: an edge joining two nonconsecutive vertices of that graph cycle. The word "induced" matters: the induced subgraph on the chosen vertices must contain exactly the cycle's edges, with no chords. Triangles are allowed. This definition concerns adjacency, independently of how the graph is drawn.

For the square cycle graph $C_4$, take vertex set $\{a,b,c,d\}$ and set of edges $\{ab,bc,cd,da\}$, where $ab$ abbreviates $\{a,b\}$. Its graph neighbourhoods are $N(a)=N(c)=\{b,d\}$ and $N(b)=N(d)=\{a,c\}$. The square is an induced cycle, so $C_4$ is not a chordal graph. Add the single edge $ac$: now $N(a)=\{b,c,d\}$, $N(b)=\{a,c\}$, $N(c)=\{a,b,d\}$, and $N(d)=\{a,c\}$. The only possible four-vertex graph cycle has chord $ac$, so this new graph is a chordal graph. Its maximal cliques are exactly $\{a,b,c\}$ and $\{a,c,d\}$.

Connect these two maximal cliques by a single edge labelled with their intersection $\{a,c\}$. The result is a junction tree, also called a clique tree: its nodes are maximal cliques, and the nodes containing any fixed original vertex induce a connected graph inside the tree. Here $a,c$ occur in both nodes, while $b,d$ each occur in just one. This is the running intersection property. More generally, a nonempty connected graph is a chordal graph exactly when its maximal cliques admit such a tree; a disconnected chordal graph can be represented by one such tree per connected component of a graph.^[ref]

A chordal graph need not be a planar graph: the complete graph $K_5$ is a chordal graph, since every pair of distinct vertices is adjacent, but its ten edges violate the planar graph edge bound $|E|\le 3|V|-6=9$. Conversely, even a plane drawing whose bounded faces are triangles can hide an induced cycle: a wheel graph with a four-vertex rim and a central vertex joined to the whole rim still has the rim as an induced cycle. Adding chords to obtain a chordal graph is called triangulation of an undirected graph; this is an adjacency condition, rather than a requirement about planar faces.

Why is this structure useful? The maximal cliques collect local interactions, and the running intersection property makes their overlaps sufficient for consistent communication. For random variables $x_a,x_b,x_c,x_d$ with finite state sets, a probabilistic graphical model of the square-plus-diagonal form can havewhere the two nonnegative clique potentials have a positive normalizing constant $Z$. Eliminating $x_b$ produces the two-variable junction-tree sum-product messageThe shared clique $\{a,c\}$ carries everything needed from the eliminated side. For $q$ possible states per random variable, this example uses two sums over $q^3$ configurations after reusing the message, rather than directly summing over $q^4$ configurations. The example's message is an exact finite sum, with no simulated data. Large maximal cliques still make exact inference expensive; chordal graphs provide a decomposition, not a universal guarantee of cheap inference.^[ref]

The 2-core is what remains of a finite simple graph after repeatedly removing every vertex with fewer than two surviving graph neighbours. It strips away dangling trees while keeping the part that can support itself under this local rule. Precisely, for an undirected graph $G=(V,E)$, its 2-core is the unique maximum by set inclusion induced subgraph $G[S]$ such thatThe empty vertex set is allowed: the condition is then vacuous, without needing to define the minimum degree of the empty graph. "Maximum by inclusion" means that $S$ contains every other vertex set satisfying the condition. It is stronger than merely saying that one chosen set cannot be enlarged: the 2-core simultaneously contains all possible qualifying induced subgraphs. In this particular family, every inclusion-maximal qualifying set does equal that unique maximum; the union argument in why the 2-core is unique explains why. ^[ref]

For a complete worked example, let $ab$ denote the edge $\{a,b\}$ and takeThe triangle in a graph $abc$ has a branching tail attached at $c$, and $z$ is an isolated vertex. In alphabetical order the initial degrees of vertices are $(2,2,3,3,2,1,1,0)$. Deleting $f$ turns $e$ into a leaf of a graph; deleting $g$ leaves $d$ with degree of a vertex two; deleting $z$ changes no other degree of a vertex. Now delete $e$, which makes $d$ a leaf of a graph, and finally delete $d$. Exactly the three edges of $abc$ remain: $C_2(G)=G[\{a,b,c\}]$.

A forest has empty 2-core: every nonempty finite forest has an isolated vertex or a leaf of a graph, so deletion cannot stop at a nonempty remainder. In particular, an isolated edge, an isolated vertex, a path graph, and the empty graph all have empty 2-core. Every cycle graph is its own 2-core. Two disjoint triangles in a graph also form their own 2-core, so a 2-core need not be a connected graph; attaching a tree to either triangle changes neither surviving triangle.

Here excess means edges minus vertices. For a connected graph it is one less than the number of independent cycles. Deleting a leaf and its incident edge, or suppressing a degree-two vertex, preserves excess. This convention differs by one from the cyclomatic number for connected graphs.

A geometric spanner is a weighted graph on points in Euclidean space, with edge weights equal to their Euclidean distances, in which every pair has a graph path of length at most $t$ times its direct distance. Its stretch factor is the largest ratio $d_G(u,v)/\Vert u-v\Vert$, where $d_G$ is shortest-path distance. A square's four perimeter edges, without diagonals, give stretch factor $\sqrt{2}$: adjacent points have ratio one, and diagonal pairs have route length $2$ instead of $\sqrt{2}$. The aim is to retain short routes with fewer edges than a complete graph. ^[ref].

For smooth $2\pi$-periodic $f$, the equation $u_t-u_{xx}+u=f$ is the negative $L^2$ gradient flow of $I_f[u]=\frac{1}{2}\int (u_x^2+u^2-2fu)dx$. Periodic integration by parts gives $d{I}_f/dt=-\int u_t^{2}dx$. Its unique equilibrium has Fourier coefficients $f_n/(1+n^2)$, and every transient coefficient decays as $e^{-(1+n^2)t}$. Thus the flow converges to the unique minimizer of the energy.

For a Morse function, a downward gradient flow is Morse-Smale if every unstable manifold meets every stable manifold transversely. An intersection between points whose indices differ by one has dimension one; quotienting by time translation gives isolated connecting trajectories. Choosing orientations of the unstable manifolds assigns signs to these trajectories and defines the differential of the Morse-Smale complex.

Intraislet glucagon signaling is critical for maintaining glucose homeostasis by Lu Zhu and others tested whether local glucagon supports insulin release. For human pancreatic islets, a computer-controlled flow system delivered a buffer solution at $1\mathrm{ml}/\min$ through a chamber holding 500 pancreatic islets on a nylon filter at $37{}^{\circ }\mathrm{C}$. A fraction collector sampled the outgoing fluid. With an amino acid mixture present, the experiment changed glucose from $3$ to $16.7\mathrm{mM}$ and compared GLP-1 receptor blockade with fluid lacking the blocker. The readout was released insulin and glucagon: blockade reduced glucose-stimulated insulin release without significantly changing glucagon release. ^[ref]

Complementary mouse experiments suppressed alpha cell activity using an engineered G protein-coupled receptor. ELISA assays of minute-by-minute effluent samples measured insulin and glucagon concentrations, providing the hormone release readout. Drug-treated control pancreatic islets lacking that engineered receptor checked for drug effects; adding glucagon restored insulin release in the suppressed preparation. Together, blockade and rescue support local signal transduction from alpha cells to beta cells. Isolated pancreatic islets omit intact circulation and nervous input; the human preparation came from five donors, and blocker specificity and donor variation limit generalization. A chamber response does not directly measure whole-body blood glucose control. ^[ref]