Codex @codex  0

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.

A spanning subgraph in which every vertex has vertex degree two. In a finite simple graph, its connected components of a graph are graph cycles. Removing a perfect matching from a cubic graph leaves a 2-factor.

An acyclic orientation is an orientation of a graph whose resulting directed graph has no directed cycle, hence is a Directed acyclic graph. A directed cycle must follow every arrow around its closed route. A cycle in a graph in the skeleton of a directed graph only requires the corresponding undirected edges; their arrows need not agree around the route.

For the same triangle in a graph with vertex set $\{A,B,C\}$ and edges $AB,BC,AC$, compareBoth have an undirected cycle in a graph in their skeleton of a directed graph. Only $D_2$ has a directed cycle. In $D_1$, $C$ has no outgoing directed edge, so a route cannot continue from $C$ back to $A$.

Thus an acyclic orientation does not require its underlying undirected graph to be a forest. Every orientation of a graph of a forest is acyclic, because a directed cycle would give an undirected cycle in a graph. Conversely, every finite simple graph, including one with many cycles in a graph, admits at least one acyclic orientation by the following ordering construction. On this triangle in a graph, six of the eight orientations of a graph are acyclic; the other two follow the directed cycle in opposite senses.

An adjacency list represents a graph by keeping, for each vertex $v$, a collection $\mathrm{Adj}[v]$ of the vertices reached by its outgoing edges. An array indexed by vertex identifiers can locate each collection; the collection itself may use a linked list or an array. In an undirected graph, each nonloop edge supplies an entry at both endpoints.^[ref]

For a worked example, take the simple graphwhere $AB$ denotes the unordered pair $\{A,B\}$. Its adjacency lists, displayed in label order, areThus $C$ has three neighbours, although the graph has six vertices. Its list contains exactly the destinations available for a single step from $C$; no slots are reserved there for $C,E,F$. The fourteen neighbour entries represent seven edges, with $CD$ appearing as $D$ in $C$'s list and as $C$ in $D$'s list. The label order makes the example easy to read; an adjacency list need not be sorted.

The useful idea is to store existing connections explicitly. Neighbour enumeration can then follow exactly the possible next steps, which is what breadth-first search and depth-first search need. In a sparse graph, most pairs of vertices have no edge; adjacency lists avoid reserving a separate adjacency matrix entry for every such absence. Whether this saves work depends on the question: neighbour enumeration and testing one proposed edge have different costs.

For a directed graph, store $v$ in $\mathrm{Adj}[u]$ for the edge $u\to v$. The reverse edge $v\to u$ is separate and is stored only if it exists. Consequently, list length is outdegree, not indegree, and each directed edge contributes one entry in total. An incoming-list index is additional storage.^[ref]

Orient the seven edges of our example from earlier to later labels. The resulting directed graph hasThere are now seven entries, with outdegrees $(2,1,1,2,1,0)$. In particular, $F$ needs an empty list even though it is reached from $D,E$: incoming edges do not make $F$'s outgoing list nonempty. Replacing each directed edge by an undirected graph connection would lose this distinction.

Our running simple graph excludes self-loops and repeated edges. If those restrictions are relaxed, specify how the adjacency list encodes them. Here an undirected self-loop at $u$ contributes two copies of $u$ to $\mathrm{Adj}[u]$, matching its contribution of two to the degree of a vertex. A directed self-loop contributes one copy, and one each to outdegree and indegree. Distinct parallel edges retain distinct entries; a multigraph's list length can therefore exceed its number of distinct neighbours.^[ref][ref]

For example, add one undirected self-loop at $A$ to the seven-edge example. Its list becomes $(B,C,A,A)$, the vertex degree of $A$ becomes four, and the total entry count becomes sixteen for eight edges. If an application instead stores a self-loop once, it must account for its doubled undirected vertex degree separately. In a weighted graph, an entry can be an ordered pair $(v,w)$ meaning destination $v$ and weight $w$; the weight belongs to the edge, not to the destination vertex.

For a finite simple graph $G$ and a matching in a graph $M\subseteq E(G)$, $M$ is a maximum cardinality matching if and only if $G$ has no augmenting path in a matching relative to $M$. The graph need not be a bipartite graph, and the assertion concerns cardinality, not edge benefits.^[ref]

The criterion turns a global comparison with every competing matching in a graph into a search for one repair. Starting from any matching in a graph, repeatedly find and toggle an augmenting path in a matching. Each step adds one selected edge, so finiteness gives termination after at most $\lfloor |V(G)|/2\rfloor -|M|$ steps; absence of any further augmenting path in a matching certifies maximum cardinality. This is an optimality criterion, not by itself a bound on the work needed to find each graph path.

For a short proof outline, an augmenting path in a matching immediately contradicts maximum cardinality. Conversely, if another matching in a graph $N$ has $|N|>|M|$, consider the subgraph whose set of edges is $M△N$. Its vertices have degree of a vertex at most two; its nontrivial connected components are graph paths and even cycles in a graph, alternating between the two matchings in a graph. A cycle in a graph contributes equal numbers from each. Hence some graph path contributes one more edge from $N$ than from $M$ and starts and ends with edges from $N$. Its endpoints are unmatched vertices in a matching relative to $M$, yielding the required augmenting path in a matching.

A bipartite graph separates its vertices into two independent sets: every edge goes from one part to the other. Here $G=(V,E)$ is a finite simple graph and an undirected graph, with no self-loops and no repeated edges. The two parts $X,Y\subseteq V$ satisfyThus neither part contains an edge. The parts need not have equal sizes, and some pairs across them may have no edge; requiring every cross pair gives a complete bipartite graph. The independent set and cross-edge definitions are equivalent.^[ref]

For example, the six-vertex cycle graph $C_6$ with edges $12,23,34,45,56,61$ has parts $X=\{1,3,5\}$ and $Y=\{2,4,6\}$. Drawing the same graph as a hexagon or in two columns changes neither its edges nor its bipartite property. An extra isolated vertex $z$ can go in either part.

We allow either part to be empty. Consequently a graph with no edges is bipartite, even when $V=\varnothing$; choose $X=V$, $Y=\varnothing$. Here "two colours" means two colours are available, with no requirement to use both. This convention explicitly includes the empty case, whereas definitions requiring two nonempty classes need an exception. For several connected components of a graph, choose the two parts separately in each graph component and take their unions. In a nonempty connected graph that is bipartite, fixing one vertex's colour forces all others along graph paths, so its two-colour assignment is unique up to swapping the colours. Each graph component, including an isolated vertex, can be swapped independently.

The two-colourability criterion for bipartite graphs identifies these parts with the colour classes of a proper vertex colouring: assign colour $0$ to $X$ and colour $1$ to $Y$, so adjacent vertices have different colours. More surprisingly, the odd-cycle characterization of bipartite graphs turns a global requirement into one precise obstruction:This statement is for the finite undirected graph and simple graph model above; a graph cycle has distinct vertices except for the repeated starting vertex. Along a graph cycle in a bipartite graph, colours alternate, so returning to the starting colour takes an even number of edges. Therefore any odd cycle, whether or not other edges join its vertices, prevents a bipartite split.^[ref]

Breadth-first search supplies the converse constructively. Start an uncoloured vertex $s$ with colour $0$, and use a FIFO queue to explore its graph component. When an edge $uv$ first discovers $v$, give $v$ the opposite colour to $u$, record $u$ as its parent in a rooted tree, and enqueue $v$. If both endpoints of any scanned edge already have the same colour, stop with a conflict. Restart from an uncoloured vertex until every graph component has been examined. If no conflict occurs, all edges cross the two colour classes, which are the required independent sets.^[ref]

A conflict also explains the failure. In the rooted tree produced by breadth-first search, let $d(v)$ be the graph distance from $s$. The colour of $v$ is its distance's integer parity. An edge $uv$ in an undirected graph satisfies $|d(u)-d(v)|\le 1$, so equal colours force $d(u)=d(v)$. Follow the two parent chains upward to their lowest common ancestor $w$, discard the shared graph path from $s$ to $w$, and join the remaining two graph paths with the conflict edge $uv$. The result is a genuine graph cycle withedges, an odd integer. The two branches have no shared vertices except $w$, so this is more than a closed walk. This odd cycle is a certificate that anyone can check directly, using only its listed vertices and edges.

In the example, breadth-first search from $s$ gives $d(w)=1$, $d(a)=d(b)=2$, and $d(u)=d(v)=3$. The conflict edge $uv$ closes the odd cycle $w,a,u,v,b,w$, with five edges. The common edge $sw$ is excluded. Thus the same procedure returns either two independent sets covering $V$, or an explicit odd cycle. With adjacency lists and constant-time FIFO queue operations, its time complexity is $O(|V|+|E|)$ in Big O notation, with $O(|V|)$ additional storage.^[ref]

The two parts often have a practical meaning: workers and jobs, with an edge exactly when a worker can perform a job. A matching in a graph chooses compatible worker–job pairs with no reused endpoint; merely being bipartite does not guarantee enough compatible pairs. Hall's marriage theorem characterizes when every worker can be matched, and the assignment problem adds costs to seek an optimal assignment. These connections make the bipartite structure useful after recognition, as the starting point for selecting edges under constraints.

If a finite simple graph is a connected graph, a bipartite graph, and a planar graph, with $n\ge 3$ vertices, then $m\le 2n-4$. Every facial boundary walk has even length and length at least three, hence at least four. Thus $4f\le 2m$; substitute the Euler formula for a connected planar graph.^[ref]

The square cycle graph attains equality: $4=2\cdot 4-4$. The three-vertex graph path also attains equality: $2=2\cdot 3-4$. Its repeated bridges in a graph illustrate why counting facial boundary walk length correctly matters. Neither bound applies unchanged to a multigraph: two vertices may support arbitrarily many parallel edges in a plane graph.

A branch set of a graph minor is the connected region representing one target vertex. For finite simple graphs $G$ and $H$, a witness to $H\preccurlyeq G$ assigns a nonempty set $B_x\subseteq V(G)$ to each $x\in V(H)$, such that the sets are pairwise disjoint, each induced subgraph $G[B_x]$ is a connected graph, and every $xy\in E(H)$ has a witnessing edge of $G$ between $B_x$ and $B_y$. Extra edges between branch sets of a graph minor are allowed: they can be deleted. Unused vertices are also allowed.^[ref]

In the diagram, the host graph has vertex set $\{1,2,3,4,5,6\}$ and edgesChoose $B_A=\{1,2\}$, $B_B=\{3,4\}$, and $B_C=\{5,6\}$. Their internal edges $12,34,56$ establish connectedness. The edges $23,45,61$ witness $AB,BC,CA$, respectively, so they form a model of the complete graph $K_3$. The additional edge $24$ also joins $B_A$ to $B_B$; it supplies another witness for the same target edge, not a fourth target edge. Contracting $12,34,56$ and merging duplicate edges gives exactly $\{AB,BC,CA\}$.

The same branch sets of a graph minor also witness the path graph $A,B,C$: retain the witnesses $23,45$, and delete $61$ to remove the unwanted $AC$ adjacency. This demonstrates why the definition requires an edge for every target adjacency, without forbidding other adjacencies in the host graph. For a complete graph $K_t$, there are no unwanted pairs: its model consists of $t$ disjoint connected branch sets of a graph minor with an edge between every pair.

To turn a model into an operation sequence, keep a spanning tree inside each $G[B_x]$, keep one witnessing edge for each edge of $H$, and delete all other edges and unused vertices. Contract each chosen spanning tree to one vertex. Disjointness prevents two target vertices from merging; connectedness provides the edge contractions that merge each individual region. Conversely, track the original vertices merged into every surviving vertex during a deletion-and-edge contraction sequence. They form disjoint connected branch sets of a graph minor, and each surviving edge comes from an original edge between its two regions. A list of these regions, their connecting trees, and their witnessing edges therefore gives a directly checkable certificate.

For an integer $n\ge 2$, let ${\mathcal{T}}_n$ be the set of labelled trees with fixed vertex set $\{1,\dots ,n\}$. Each tree is a finite simple graph, with no distinguished root of a tree, and two trees are different exactly when their sets of edges differ. ThenEquivalently, this is the number of spanning trees of the complete graph $K_n$. The labelled combinatorial structure includes the fixed labels: drawings, positions, and the order in which edges are listed do not create extra trees. For $n=1$, the single vertex with no edges is the unique tree; count it separately, since the Prüfer sequence construction requires $n\ge 2$. For $n=2$, the unique tree has edge $\{1,2\}$ and corresponds to the empty Prüfer sequence. ^[ref]

For four fixed labels, there are $4^2=16$ labelled trees, but only two unlabelled trees: the star graph and the path graph. There are four star graphs, one for each choice of centre. There are $4!/2=12$ path graphs: arrange the labels along a graph path, then identify each ordering with its reversal, which describes the same set of edges. Thus $4+12=16$. For instance, star graphs centred at $1$ and at $2$ have different sets of edges even though they have the same shape.

The striking point is that connectedness and the absence of a graph cycle are global restrictions on edges, yet the answer is a power with no correction factor. The Prüfer sequence supplies a bijection that turns those restrictions into $n-2$ freely chosen labels. The rule of product then gives $n^{n-2}$ immediately. The same representation makes vertex degrees easy to count and supports uniform labelled tree generation for simulations and algorithm experiments.

Arthur Cayley's 1889 paper "A theorem on trees", published in the Quarterly Journal of Pure and Applied Mathematics, volume 23, pages 376–378, treats the counting problem and its refinement by vertex degrees. It was reprinted as paper 895 in volume XIII of his Collected Mathematical Papers, pages 26–28. This publication is the historical context for the name Cayley's formula; the name alone is not a claim of priority. ^{[ref] [ref]}

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]

For every finite simple graph, Vizing's theorem givesHere $\Delta (G)$ is the maximum degree of a graph, taken as zero when there are no vertices. A bipartite graph has the stronger equality $\chi \prime (G)=\Delta (G)$. The six-job complete bipartite graph above attains this lower bound, while the triangle in a graph attains the extra-colour alternative. The simple-graph restriction in the upper bound matters.^[ref]

The bipartite graph equality still holds for finite loopless multigraphs, with parallel edges counted separately in each vertex degree. For instance, $r$ parallel jobs between two resources need exactly $r$ slots: every pair conflicts, and $\Delta =\chi \prime =r$. For a general finite loopless multigraph, however, the simple graph upper bound can fail. Put two parallel edges on each side of a triangle in a graph. All six edges pairwise share a vertex, so each needs its own colour; every vertex has degree of a vertex four. Consequently $\chi \prime =6>\Delta +1=5$. A multiplicity-aware bound is $\chi \prime (G)\le \Delta (G)+\mu (G)$, where $\mu (G)$ is the largest number of parallel edges between a pair of vertices. The doubled triangle in a graph has $\mu =2$ and attains that bound. These statements exclude self-loops; the two-distinct-resource scheduling model excludes them too.^[ref]

For historical orientation, Graph Theory by Reinhard Diestel (Colouring preview, §5.3, p. 132) dates the bipartite equality to 1916 and Vizing's theorem to 1964. These are textbook attributions; the original papers have not been inspected here. The results state existence of optimal or nearly optimal proper edge colourings, rather than saying that arbitrary greedy choices will find them. The list-chromatic index asks the further question of success for every sufficiently large family of allowed-colour lists.

For a nonempty finite simple graph $G$, the chromatic number $\chi (G)$ is the least positive integer $k$ for which $G$ has a proper vertex graph coloring with at most $k$ colours. To establish an exact chromatic number, give a colouring using that many colours and explain why fewer cannot suffice. A colouring alone gives only an upper bound.^[ref]

These small graphs show why the chromatic number measures more than the presence of triangles in a graph:

For a cycle graph of even length, alternating two colours closes consistently; for an odd cycle, it does not, and a third colour on the final vertex suffices. More generally, the two-colourability criterion for bipartite graphs says that $\chi (G)\le 2$ exactly when $G$ is a bipartite graph, and the odd-cycle characterization of bipartite graphs identifies the obstruction as an odd cycle. A nonempty graph with no edges has chromatic number one; a bipartite graph with at least one edge has chromatic number exactly two.

In the pairwise-conflict scheduling model of graph coloring, $\chi (G)$ is the least number of interchangeable slots needed. This turns a drawing into an optimization question: how many groups of compatible activities are unavoidable? Greedy coloring constructs a valid grouping quickly, but its number of colours can exceed the chromatic number.

The chromatic polynomial turns a graph coloring problem into a counting problem: how many choices remain when adjacent vertices must have different colours? For a finite simple graph $G$ and a positive integer $t$, $P_G(t)$ is the number of proper vertex colorings using a fixed, distinguished palette of $t$ colours. A colouring need not use every available colour, and exchanging two palette colours generally gives a different colouring. Although $P_G$ is a polynomial, its values at arbitrary noninteger arguments are not counts of colourings.

Consider the three-vertex path graph $A$--$B$--$C$. Choose $A$ in $t$ ways, then $B$ in $t-1$ ways, then $C$ in $t-1$ ways: $A$ and $C$ may agree because they are not adjacent. The multiplication principle givesAdding the edge $AC$ makes the three-vertex complete graph $K_3$. Now $C$ must avoid both preceding colours, soWith three available colours, the path graph has 12 colourings, whereas the triangle has 6. With two colours the counts are $2$ and $0$: the extra constraint makes the triangle impossible to colour.

For a nonempty graph, the chromatic number records only the first positive integer $t$ for which $P_G(t)>0$. The chromatic polynomial also counts the choices for every larger palette. For the path the chromatic number is $2$, and for the triangle it is $3$. Counting assignments also gives a useful interpretation for scheduling: if adjacent vertices represent tasks that must use different slots, the chromatic polynomial counts the valid assignments to $t$ named slots. Adding a conflict edge can only remove assignments.

The chromatic polynomial also remembers some of the graph's structure. For a simple graph with $n\ge 1$ vertices and $m$ edges, its leading terms are $t^n-m{t}^{n-1}$; its degree of a polynomial gives the number of vertices, and its next coefficient gives the number of edges. It does not determine the graph completely. A four-vertex path graph and a four-vertex star graph are not related by a graph isomorphism, but both are trees and have chromatic polynomial $t(t-1{)}^3$.

The early connection to map colouring appears in George D. Birkhoff's article ^[ref]. For a derivation of the counting recurrence and its leading coefficients, see Paul Johnson's MAS 341 lecture on chromatic polynomials.

An $r$-regular graph is class two when its edge chromatic number exceeds $r$. For a finite simple graph, Vizing's theorem makes that edge chromatic number exactly $r+1$. An $r$-colour proper edge colouring of an $r$-regular graph would partition its edges into $r$ perfect matchings, since every vertex would see each colour exactly once.

Given an explicitly represented finite simple graph $G$ and a nonnegative integer $k$, decide whether $G$ contains a clique of size $k$. The problem is NP-complete. A polynomial-time many-one reduction from SAT first obtains conjunctive normal form by a Tseitin transformation, makes one vertex per Boolean literal occurrence, and joins noncontradictory occurrences from different Boolean clauses. A clique as large as the Boolean clause count is equivalent to a satisfying assignment.

A clique in a simple graph $G$ is a set $C$ of vertices such that every pair of distinct members is adjacent. Equivalently, its induced subgraph $G[C]$ is a complete graph. The surrounding graph need not itself be complete: a clique describes complete pairwise connectivity within a selected group.

Consider the original graph withThe set $\{a,b,c\}$ is a clique because all three pairs $ab,ac,bc$ are edges. The set $\{b,c,d\}$ is not a clique: the edge $bd$ is missing. A path in a graph connecting all selected vertices is therefore insufficient; every pair must have a direct edge.

Here the clique number is $3$. The maximum clique is $\{a,b,c\}$, but $\{c,d\}$ and $\{d,e\}$ are also maximal cliques. This distinction is useful when an algorithm stops as soon as its current clique cannot be enlarged: that stopping condition establishes maximality, while finding the largest possible clique is a separate requirement.

A closed walk is a walk with equal endpoint vertices, $v_m=v_0$. Under our convention this includes the zero-length walk $(v)$; returning after traversing at least one edge requires $m>0$. Closure imposes no other restriction on repeated vertices or edges. In a directed graph, a closed directed walk must also follow every directed edge in its permitted direction.^[ref]

In the shared simple graph, $A,F,A$ is a length-two closed walk that immediately backtracks along $AF$. It is not a trail, since $AF$ is used twice, and it is not a graph cycle. The length-six closed walk $A,B,C,A,D,E,A$ is a trail, since its six edges are distinct, but is not a graph cycle: it returns to $A$ midway through the journey. The length-three closed walk $A,B,C,A$ is a graph cycle, with all vertices distinct apart from the required endpoint repetition. In a simple graph that is an undirected graph, a graph cycle has length at least three; the two-step backtrack is excluded.^[ref]

A positive-length closed walk therefore need not reveal a graph cycle: even a tree permits an out-and-back journey on an edge. A positive-length closed trail in a simple graph does contain a graph cycle. For a proof outline, choose a shortest positive-length consecutive portion of the trail whose endpoint vertices coincide. It cannot repeat an internal vertex, since that would give a shorter such portion; it cannot have length one or two because self-loops and repeated edges are excluded. It is consequently a graph cycle. Cutting it out leaves another closed trail, possibly of length zero, so repetition partitions the original edges into graph cycles. In our six-step example these are the two triangles in a graph. A closed trail using every edge would be an Euler circuit; here $AF$ is omitted.

Counting return journeys makes closed walks useful even when they repeat edges. For a finite simple graph with adjacency matrix $M$, the walk count from powers of an adjacency matrix gives $(M^k{)}_{uv}$ length-$k$ walks from $u$ to $v$, for every nonnegative integer $k$. A proof outline is that matrix multiplication appends one allowed step, summing over the previous endpoint; $M^0$ is the identity matrix, recording the unique zero-length walk at each vertex. ConsequentlyThe trace counts closed walks with a specified starting vertex and traversal order, not distinct graph cycles. These formulas use adjacency entries, not arbitrary travel costs in a weighted graph.^[ref]

In our example, $(M^2{)}_{AA}=5$: the five length-two closed walks are $A,B,A$, $A,C,A$, $A,D,A$, $A,E,A$, and $A,F,A$. Also $(M^3{)}_{AA}=4$, going round either triangle in a graph in either direction, and $\mathrm{tr}(M^3)=12$: each of the two triangles in a graph supplies three choices of starting vertex and two directions. These exact counts for the constructed graph illustrate why return counts and graph cycle counts differ.

A closed walk naturally models a delivery or inspection journey that returns to its depot. Repeated vertices let it combine several excursions; repeated edges let it serve a dead end and return. For an Euclidean travelling salesman tour, one can first construct a closed walk visiting all locations and then use the triangle inequality to shortcut repeated visits without increasing total length. That argument assumes direct travel between the retained locations is permitted, as in a complete graph weighted by Euclidean distance; an arbitrary road network need not contain those shortcut edges.

For a vertex with $k_i\ge 2$ neighbours in a simple graph, its local clustering coefficient is $C_i=e_i/\left(\genfrac{}{}{0ex}{}{k_i}{2}\right)$, where $e_i$ counts edges among those neighbours. It is the fraction of possible neighbour-neighbour edges that are present. A common network summary averages these local coefficients, setting them to zero for degrees below two; this differs from weighting by the number of neighbour pairs.

A complete graph is a simple graph in which every two distinct vertices are joined by an edge. The finite complete graph on $n$ vertices is denoted $K_n$. Here the edges are undirected, and self-loops are excluded. The usual pictures below use $n\ge 1$: $K_1$ is a single vertex, $K_2$ a single edge, and $K_3$ a triangle in a graph.^[ref]

Completeness describes all the possible pairs, rather than a drawing style. Different layouts can represent the same graph through a graph isomorphism. Crossing lines away from the drawn vertices do not add new vertices or edges.

There are $\left(\genfrac{}{}{0ex}{}{n}{2}\right)=n(n-1)/2$ unordered pairs of distinct vertices, so this is the edge count of a complete graph. Each vertex has vertex degree $n-1$. The degree-sum formula gives the same count: $2|E|=n(n-1)$. These formulas make a complete graph the upper extreme for edge counts among simple graphs of a fixed size.

This is useful when modelling pairwise relationships. If every pair of objects needs its own direct connection, ten vertices require $45$ edges, while twenty require $190$. Adding one more vertex to $K_n$ introduces $n$ further edges. This counts a specified direct-link model; it does not require every communication system to implement every relationship with a separate physical connection.

A proper vertex coloring of $K_n$ must give every vertex a different color, so its chromatic number is $n$. For $n\ge 1$, its independence number is $1$: two distinct vertices already have an edge between them. Thus complete graphs provide immediate test cases for graph coloring and independent sets.