A uniform spherical cloud with negligible pressure and velocity $\mathbf{u}=(\dot{R}/R)\mathbf{r}$ remains uniform: the continuity equation gives $\rho R^3={\rho }_{00}{R}_0^3$. The shell theorem gives interior gravitational acceleration $-(4\pi G\rho /3)\mathbf{r}$, so its outer radius satisfies the displayed equation, with fixed mass $M=4\pi {\rho }_{00}{R}_0^3/3$. Collapse from rest has ${\dot{R}}^2=2GM(1/R-1/R_0)$. Writing $C^2=2GM/R_0$, its cycloid parametrization is $R=R_0(1+\cos \varphi )/2$ and $Ct=R_0(\varphi +\sin \varphi )/2$, for $0\le \varphi \le \pi$. Complete collapse occurs after $\sqrt{3\pi /(32G{\rho }_{00})}$. This Newtonian dust solution ceases to be a regular fluid configuration at zero radius.

A pseudoforest is an undirected graph in which every connected component of a graph contains at most one cycle in a graph. Thus each component is a tree or a unicyclic component. A finite tree component has one fewer edge than vertices; a finite unicyclic component has equally many edges and vertices.

Let a finite simple graph on $n\ge 3$ vertices have nondecreasing degree sequence $d_1\le \cdots \le d_n$. Pósa's theorem gives the sufficient conditionfor a Hamiltonian cycle. It controls the low-degree tail of the whole sequence, rather than requiring every vertex to have large degree.

For example, any graph satisfying Dirac's theorem, with minimum degree at least $n/2$, satisfies this condition. The condition is sufficient rather than necessary: the cycle $C_6$ is Hamiltonian but has $d_2=2$. Longest-path rotation is a related proof technique; it is distinct from the degree-sequence statement itself.

A vertex cycle cover is a collection of cycles whose union contains every vertex of a graph; its cycles can overlap. A cycle cover of a directed graph additionally requires directed, vertex-disjoint cycles, and a spanning circuit family can allow overlaps.

A squaregraph has a plane embedding in which every bounded face has four sides and every interior vertex has degree at least four. Its outer face may have more than four sides, so this definition differs from a planar quadrangulation requiring every face to have degree four.

A prism graph joins two copies of a cycle graph by matching corresponding vertices. The triangular prism graph is the three-cycle case, with six vertices and nine edges.

The Erdős-Gallai theorem characterizes degree sequences of finite simple graphs. A nonincreasing sequence of nonnegative integers $d_1\ge \cdots \ge d_n$ is realizable exactly when its sum is even and, for every $1\le k\le n$,Necessity comes from counting the edges incident with the first $k$ vertices: edges within that set contribute at most $k(k-1)$ to the degree sum, and each outside vertex can contribute at most $\min (k,d_i)$. The theorem's substance is that these necessary conditions are sufficient.

For example, $(2,2,2)$ is realized by a triangle in a graph. In contrast, $(3,3,1,1)$ has even sum but fails the $k=2$ inequality: $6>2+1+1$. An even sum alone therefore does not guarantee a degree sequence.

Every graph on $n\ge 3$ vertices with minimum degree at least $n/2$ has a Hamilton cycle.

A matching in a graph is a set $M$ of edges of an undirected graph with no shared endpoints: each vertex has capacity for at most one selected edge. It describes simultaneous compatible pairs, such as jobs assigned to distinct available workers, or tasks each occupying two resources that cannot be shared. The empty set is a valid matching in a graph.^[ref]

For a finite simple graph $G=(V,E)$, write $x_e=1$ when $e$ is selected and $x_e=0$ otherwise. The vertex capacity constraint is exactlyThese are constraints on a discrete selection, not a requirement that every vertex be used. A matching in a graph with matching saturation of all vertices is a perfect matching; an unmatched vertex in a matching uses none of its capacity.

The objective must be specified separately. A maximum cardinality matching selects as many edges as possible; a maximum-weight matching selects the greatest total benefit; a minimum-weight perfect matching minimizes cost while requiring every vertex to be paired. A maximal matching only says that no additional edge fits alongside the current choices. The four-vertex path graph below separates these notions: choosing the middle edge blocks both outer edges, yet replacing it by those two edges pairs more vertices.

This model is useful because conflicts are local at vertices, while the quality of a selection can depend on coordinated changes along a whole augmenting path in a matching. A greedy matching gives a quick feasible selection; Berge's theorem explains when searching for such changes has reached a maximum cardinality matching. Repeating the pairing problem over time leads instead to proper edge colouring, where each time slot is a matching in a graph.

Spectral graph theory studies a graph through eigenvalues and eigenvectors of associated matrices, especially its adjacency matrix and graph Laplacian. A graph eigenvalue usually means an adjacency eigenvalue unless another matrix is specified.

For an undirected graph, the Laplacian $L=D-A$ satisfies $x^{T}Lx={\sum }_{uv\in E}(x_u-x_v{)}^2$. Its kernel therefore consists of vectors constant on each connected component, so the multiplicity of zero equals the number of components. This makes a discrete connectivity property visible in linear algebra. Nonzero eigenvalues further quantify mixing, expansion, and the cost of varying across edges.

The distance $d(u,v)$ between connected vertices is the least length of a path joining them.

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.