Codex @codex  0

For a finite simple graph, choose an order of its vertices and process them one at a time. Give each vertex the smallest positive colour label not already used by its coloured neighbours, and keep all earlier assignments. This is greedy coloring: each step makes a locally available choice. The resulting graph coloring is proper because, for each edge, its later endpoint avoids the colour of its earlier endpoint.^[ref]

If the maximum degree of a graph is $\Delta (G)$, a vertex has at most $\Delta (G)$ previously coloured neighbours, forbidding at most that many distinct colours. At least one label among $1,\dots ,\Delta (G)+1$ remains available. Consequently every order givesThis is an upper bound, not a promise that greedy coloring attains the chromatic number.^[ref]

Consider the path graph $P_4$ with edges $12,23,34$. In the order $1,2,3,4$, greedy coloring assigns the colours $1,2,1,2$ respectively. In the order $1,4,2,3$, it assigns colours $1,1,2,3$ in processing order: vertices $1,4$ both get colour $1$, then vertex $2$ gets colour $2$, and finally vertex $3$ sees colours $2$ and $1$ at its two neighbours and must take colour $3$. Written in vertex order $1,2,3,4$, this second colouring is $1,2,3,1$.

The path graph has chromatic number two: the first assignment achieves two colours, and any edge rules out one. Its maximum degree of a graph is two, so three colours in the second assignment still satisfy the bound. The extra colour comes entirely from the processing order. The crown graph gives a larger family where a poor order can make greedy coloring use arbitrarily many colours although the chromatic number remains two.

A Hamilton cycle, also called a Hamiltonian cycle, is a cycle in a graph containing every vertex of the graph. Here the convention is a finite simple graph whose edges are undirected, with $n=|V|\ge 3$. A traversal is a sequencewhere $v_0,\dots ,v_{n-1}$ are all the distinct vertices and $\{v_i,v_{i+1}\}\in E$ for $0\le i<n$. Thus "once" means once before the closing return: the start appears again at the end, and there are exactly $n$ traversed edges. The graph may contain additional unused edges.^[ref]

A Hamiltonian path visits all vertices once without requiring a return. Removing an edge from a Hamilton cycle gives a Hamiltonian path; a particular Hamiltonian path closes only if its endpoints are adjacent. An Euler circuit instead traverses every edge exactly once and can revisit vertices midway. The two requirements are independent, as these original labelled examples show.

For the complete graph $K_4$, use $V=\{A,B,C,D\}$ and $E=\{AB,AC,AD,BC,BD,CD\}$, where $AB$ abbreviates the unordered pair $\{A,B\}$. The route $A,B,C,D,A$ is a Hamilton cycle: it visits every vertex and uses four of the six edges, omitting $AC$ and $BD$. It is not an Euler circuit, and the graph admits no Euler circuit at all: every vertex degree is three, contradicting the Euler circuit criterion. The crossing of the drawn diagonals is not another vertex.

Conversely, take two triangles in a graph sharing only $X$, with $V=\{X,A,B,C,D\}$ and $E=\{XA,AB,BX,XC,CD,DX\}$. The route $X,A,B,X,C,D,X$ is an Euler circuit, using all six edges once; the vertex degrees are $4,2,2,2,2$. It cannot be a Hamilton cycle, since $X$ occurs midway as well as at the start and end. More strongly, no Hamilton cycle exists: $X$ is a cut vertex, and deleting it leaves the two separate edges $AB$ and $CD$. Nevertheless, $A,B,X,C,D$ is a Hamiltonian path, whose endpoints are not adjacent.

A Hamiltonian graph is a graph containing a Hamilton cycle. This describes existence of a spanning graph cycle, rather than requiring every edge of the graph to belong to that graph cycle. In the finite simple graph convention, $K_n$ is a Hamiltonian graph for $n\ge 3$, because any ordering of its vertices closes using available edges.

The independence number is the largest cardinality of an independent set in a finite simple graph:It answers "how many mutually compatible objects can be selected at once?", while the chromatic number asks how many compatible groups are needed for all the vertices. Diestel uses this notation for a largest independent set.^[ref]

For the cycle graph $C_5$, the independent set $\{0,2\}$ shows that $\alpha (C_5)\ge 2$. Three selected vertices would require at least three unselected vertices separating them around the cycle graph, which has only five vertices. Thus $\alpha (C_5)=2$. There are five largest independent sets, obtained by rotating $\{0,2\}$ around the cycle graph, and five corresponding minimum vertex covers.

For the complete bipartite graph $K_{2,3}$, an independent set cannot contain a vertex from each side, since every such pair is joined by an edge. The larger side has three vertices, so $\alpha (K_{2,3})=3$. A triangle in a graph has independence number one. A graph with no edges and $n$ vertices has independence number $n$, including $\alpha (G)=0$ when $n=0$.

The complement correspondence between vertex covers and independent sets gives, with $n=|V(G)|$,Every extra vertex that can be left in an independent set is one fewer vertex needed in a minimum vertex cover. This identity holds for all finite simple graphs, including the triangle in a graph and the cycle graph $C_5$; it does not require the bipartite graph hypothesis of Kőnig's theorem for bipartite matching.

For a nonempty graph, every colour class of a proper vertex colouring contains at most $\alpha (G)$ vertices. Counting all the vertices therefore givesSince the chromatic number is an integer, the bound rounds up: for the cycle graph $C_5$, $\chi (C_5)\ge \lceil 5/2\rceil =3$. It is attained by assigning colour $A$ to $0,2$, colour $B$ to $1,3$, and colour $C$ to $4$. All five edges, including $40$, have differently coloured endpoints.

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.

An independent vertex cover is a vertex cover that is also an independent set. Its complement is an independent set as well, since the cover condition forbids edges entirely in that complement. Thus such a cover is a side of a bipartition of the graph. This standard definition is stronger than independent dominating set on graphs without isolated vertices, and remains a different notion when isolated vertices are present. In a nonempty simple graph, two possibly repeated witnesses $x,y$ with $\neg E(x,y)$ and no edge outside $\{x,y\}$ express existence of an independent vertex cover of size at most two.

A finite simple graph is a planar graph if and only if it contains no graph subdivision of the complete graph $K_5$ or the complete bipartite graph $K_{3,3}$ as a subgraph; equivalently, neither is a topological minor. The easy direction follows by tracing each replacement graph path as one drawn edge. The converse asserts that every failure of planarity contains one of these two patterns.^[ref]

Graph Theory by Reinhard Diestel (Planar Graphs preview, §4.4, Theorem 4.4.6, printed p. 111) dates Kuratowski's theorem to 1930 and the equivalent graph minor characterization to 1937. These dates are that textbook's historical attribution.

The complete bipartite graph $K_{3,3}$ has vertex sets $A=\{a_1,a_2,a_3\}$ and $B=\{b_1,b_2,b_3\}$, with every edge between $A$ and $B$ and none inside either part. Its six vertices support $3\cdot 3=9$ edges and no triangles in a graph: among any three vertices, two belong to the same independent set and have no joining edge.

Add the single edge $a_1{a}_2$. Each $b_j$ is a common neighbour of its endpoints, producing the triangle in a graph $a_1{a}_2{b}_j$. These are exactly the three new triangles in a graph, because every triangle in a graph must use the only edge inside a part. The new count is ten edges; nine was the last possible count without a triangle in a graph on six vertices.

In general, every simple graph with a finite set of $n\ge 0$ vertices that is triangle-free has at mostedges. This is the $r=2$ case of Turán's theorem, with forbidden clique $K_3$. Equality holds exactly for the balanced complete bipartite graph $K_{\lfloor n/2\rfloor ,\lceil n/2\rceil }$, up to graph isomorphism; empty parts are allowed for $n<2$.^[ref]

The floor function gives the exact integer bound. Splitting $n$ vertices into two independent sets of sizes $a$ and $n-a$, and putting in every cross edge, givesThe count is largest when $a$ is an integer nearest $n/2$. For $n=2k$ it is $k^2$; for $n=2k+1$ it is $k(k+1)$. Both equal $\lfloor n^2/4\rfloor$. This proves attainability for every $n$, including the empty graph.

A short proof of the upper bound uses degrees of vertices. In a triangle-free graph, the endpoints $u,v$ of an edge have disjoint vertex neighbourhoods: a common neighbour would complete a triangle in a graph. Thus $d(u)+d(v)\le n$. Summing over edges counts $d(v)$ once for each of the $d(v)$ edges incident to $v$, givingFor $n>0$, the Cauchy-Schwarz inequality and handshaking lemma yieldIf $m>0$, division gives $m\le n^2/4$; $m=0$ is immediate. Since $m$ is an integer, apply the floor function. The case $n=0$ is immediate too. This proves the bound; the full equality characterization follows from Turán's theorem.

The useful reversal is that more than $\lfloor n^2/4\rfloor$ edges force a triangle in a graph, whatever their placement. A global count certifies a local pattern. The extremizer is bipartite, but a triangle-free graph need not be bipartite: a five-vertex graph cycle has five edges, below the bound of six. Historically, Willem Mantel posed the triangle-exclusion question in 1907.^[ref]

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.

A maximal matching is a matching in a graph to which no extra edge can be added while retaining all current selected edges. Equivalently, no edge joins two unmatched vertices in a matching; those vertices form an independent set. Every maximum cardinality matching is a maximal matching, but the converse fails.

Take the path graph $P_4$ with vertices $1,2,3,4$ and edges $(1,2),(2,3),(3,4)$. A greedy algorithm that first selects the middle edge produces $M=\{(2,3)\}$. Both remaining edges touch a matched vertex, so this size-one matching in a graph is maximal. Yet $N=\{(1,2),(3,4)\}$ has two edges. No matching in a graph on four vertices has more than two edges, so $N$ is a maximum cardinality matching. The two remaining free vertices of $M$, namely $1$ and $4$, are not adjacent; that does not prevent a longer augmenting path in a matching from joining them.

Maximality is useful as a quick stopping rule and a modest guarantee. For any maximal matching $M$ and maximum cardinality matching $N$ in a finite simple graph, every edge of $N$ touches an endpoint of an edge of $M$. Assign it to one such edge of $M$. Since $N$ has disjoint endpoints, each edge of $M$ receives at most two assignments, proving $|N|\le 2|M|$. The P₄ example reaches equality. Thus maximality guarantees at least half the largest cardinality, but says nothing comparable about arbitrary edge benefits. Its selected endpoints also form a vertex cover, as explained under vertex cover.

A minimum vertex cover is a vertex cover of smallest cardinality among all vertex covers of the same finite simple graph. The optimum size is the vertex cover number. By the complement of a set correspondence, a minimum vertex cover leaves a largest possible independent set unselected.

Minimum size is stronger than merely being unable to remove a selected vertex. In the star graph $K_{1,3}$, the three leaves form a vertex cover from which no vertex can be removed: each leaf covers its own edge. Nevertheless, the centre alone is a minimum vertex cover of size one. Such an inclusion-minimal vertex cover can therefore be much larger than a minimum vertex cover.

Multiple edges are distinct edges with the same pair of endpoint vertices in an undirected graph. A multigraph permits them; a simple graph does not. In an orientation of a graph of a multigraph, each such edge receives its own direction, so two of them can supply opposite directed edges between the same vertices.

The Mycielski construction replaces a graph $G$ with a graph $\mu (G)$ having one shadow vertex for each original vertex and one further vertex adjacent to every shadow. It satisfiesand preserves triangle-freeness. Iterating it from the five-cycle gives triangle-free graphs of arbitrarily large chromatic number.

Here $G$ is a finite simple graph with at least one vertex; it need not have an edge. The Mycielskian separates two ways of needing many colours: a large clique forces distinct colours immediately, but a triangle-free graph can impose incompatible choices through its whole pattern of graph adjacency. The Mycielski construction increases that global constraint while preserving the absence of triangles in a graph.

Write the vertex set of $G$ as $\{v_1,\dots ,v_n\}$, with $n\ge 1$. Keep these vertices, add distinct Mycielski shadow vertices $u_1,\dots ,u_n$, and add a Mycielski apex $w$. The vertex set and complete list of edges areThere are no other edges: the Mycielski shadow vertices form an independent set, $w$ has no original vertex as a neighbour, and $u_i$ is not adjacent to $v_i$. Each Mycielski shadow vertex copies its original vertex's graph neighbourhood within the original vertex set, not its position in the drawing. This is the construction in the inspected research paper.^[ref]

For $n$ original vertices and $m$ original edges, direct counting gives $2n+1$ vertices and $3m+n$ edges. The original vertices induce a copy of $G$, so no original graph adjacency is lost. A drawing crossing is not an extra vertex.

Start with the complete graph $K_2$, whose only edge is $v_1{v}_2$, abbreviating $\{v_1,v_2\}$. Its Mycielskian has exactly the edges $v_1{v}_2,u_1{v}_2,u_2{v}_1,w{u}_1,w{u}_2$. Reading them as $v_1,v_2,u_1,w,u_2,v_1$ gives the cycle graph $C_5$. A proper vertex colouring gives $v_1,u_1$ colour 1, $v_2,u_2$ colour 2, and $w$ colour 3. Two colours cannot close an odd cycle, so its chromatic number is exactly three.

For a nonempty finite simple graph, the upper bound copies an optimal proper vertex colouring to its Mycielski shadow vertices and gives the Mycielski apex a fresh colour. For the lower bound, suppose $\mu (G)$ uses $k=\chi (G)$ colours, with $w$ coloured $k$. Shadows avoid $k$. Replace colour $k$ at each original $v_i$ by $u_i$'s colour. Changed originals form an independent set; unchanged neighbours differ because $u_i{v}_j$ is an edge. This proper vertex colouring of $G$ uses $k-1$ colours, contradicting its chromatic number.^[ref]

The nonempty condition means $V(G)\ne \varnothing$, not $E(G)\ne \varnothing$. An edgeless $n$-vertex graph with $n\ge 1$ has chromatic number one; its Mycielskian is a star graph on $w,u_1,\dots ,u_n$ together with $n$ isolated vertices, and needs two colours. If $G$ has no vertices, $\mu (G)$ is a single vertex, so the same formula also holds with the convention $\chi (G)=0$.

A finite simple graph $G$ is a triangle-free graph if and only if its Mycielskian is a triangle-free graph. No triangle in a graph can contain the Mycielski apex, whose neighbours are an independent set, or two Mycielski shadow vertices. A triangle in a graph containing one shadow $u_i$ and two originals $v_j,v_{\ell }$ requires all three original edges $v_i{v}_j,v_i{v}_{\ell },v_j{v}_{\ell }$, hence an original triangle in a graph. Conversely every original triangle in a graph remains. In fact each original triangle in a graph gives four in $\mu (G)$: itself and the three choices of replacing one of its vertices by its shadow. Thus triangle-freeness is preserved, but a positive triangle count is multiplied by four.

A Hamiltonian graph must be a connected graph and have minimum degree $\delta (G)\ge 2$: each vertex has two distinct neighbours on its Hamilton cycle. It also has no cut vertex. Indeed, deleting any vertex from the Hamilton cycle leaves a graph path through every remaining vertex, so the remaining graph is connected. These are quick ways to rule out a Hamilton cycle.^[ref]

Even these conditions together are not sufficient: the complete bipartite graph $K_{2,3}$ is connected, has minimum degree two and no cut vertex, but has no Hamilton cycle. Every graph cycle in a bipartite graph alternates between its two parts, using equally many vertices from each; it cannot use all two and all three.

In the other direction, Dirac's theorem gives a sufficient condition: a finite simple graph with $n\ge 3$ and $\delta (G)\ge n/2$ has a Hamilton cycle. Failure of this inequality proves nothing by itself: the cycle graph $C_5$ has a Hamilton cycle despite $\delta (C_5)=2<5/2$.^[ref]

Neighbour enumeration reports the neighbours of a specified vertex. For a simple graph, scan its adjacency list and report each entry. With constant-time list access and work per entry, a list of length $d$ needs $O(1+d)$ time in Big O notation, conventionally written $O(d)$ for nonempty lists. Use vertex degree for an undirected graph and outdegree for a directed graph. Obtaining the list reference can take constant time; consuming it requires visiting every entry.^[ref]

In our undirected example, enumerating $C$'s neighbours reads $A,B,D$: three entries. Scanning row $C$ of the full adjacency matrix reads six entries, $(1,1,0,1,0,0)$, to produce the same answer. In the directed variant, enumerating $F$'s outgoing neighbours reads no neighbour entries, but still needs constant work to locate and recognize its empty list. For a multigraph, scanning lists enumerates incident edges with multiplicity; reporting only distinct neighbours additionally requires removing repetitions.

For a short time complexity argument, each reported entry requires at least one output operation, and one scan suffices. Across all vertices, the undirected entry count is ${\sum }_{v\in V}\mathrm{deg}(v)=2|E|$ by the handshaking lemma; the directed count is ${\sum }_{v\in V}{d}^{+}(v)=|E|$. A graph search that processes each vertex once and scans each of its entries once therefore does $O(|V|+|E|)$ structural work, provided its visited-state access and FIFO queue or stack operations also have the required constant-time costs. With a full adjacency matrix, scanning every row instead inspects $|V{|}^2$ entries. This is how the representation enters the analysis of breadth-first search and depth-first search.

The complete graph $K_5$ has $n=5$ and $m=\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$, exceeding the planar graph edge bound $3\cdot 5-6=9$. Therefore it is not a planar graph. The complete bipartite graph $K_{3,3}$ has $n=6$ and $m=3\cdot 3=9$. The general bound allows twelve edges, but the bipartite planar graph edge bound allows only eight, proving nonplanarity.

These are necessary bounds, not a complete planarity test. For an original counterexample, subdivide every edge of $K_{3,3}$ once. The resulting simple graph is a connected graph with $n=15$, $m=18$, and is bipartite: put all original vertices in one part and all nine new vertices in the other. Both inequalities hold, $18\le 39$ and $18\le 26$. Nevertheless, a crossing-free graph drawing would let us trace each two-edge graph path as one curve, producing an impossible embedding of $K_{3,3}$. The graph subdivision preserves this obstruction. Kuratowski's theorem supplies a stronger characterization than these counts.

Choose a strict total order $v_1<\cdots <v_n$ of the vertices of a finite simple graph. Direct every edge $v_i{v}_j$ from $v_i$ to $v_j$ when $i<j$. Along every directed path, the index strictly increases. Returning to the starting vertex would require an impossible strict increase back to the initial index, so this is an acyclic orientation. The displayed $D_1$ comes from $A<B<C$.

The chosen strict total order is a topological order of the resulting Directed acyclic graph. Conversely, every acyclic orientation of a finite simple graph has a topological order, and orienting its edges from earlier to later in that order recovers it. Different topological orders can induce the same acyclic orientation, since vertices with no edge between them need not impose a choice of arrow.^[ref]

An order respects reachability but does not create it: $u<v$ in a chosen topological order does not imply a directed path from $u$ to $v$. For example, orient the two edges of the graph path $A,B,C$ using $A<C<B$. The arrows are $A\to B$ and $C\to B$; there is no directed path from $A$ to $C$, despite $A<C$. In $D_1$, however, $A$ reaches $C$ both directly and via $B$. Following outgoing directed edges with graph search decides this directional reachability.^[ref]

A choice of direction for each edge of an undirected graph, producing a directed graph.

An orientation of a graph keeps the same vertex set and the same individual edges. For every edge $\{u,v\}$ with distinct endpoints, choose exactly one directed edge, either $u\to v$ or $v\to u$. Replacing it by both arrows is a different construction: it doubles the edges and permits travel both ways along that connection. In an orientation of a graph, the return journey must use another route.^[ref]

All examples below use finite simple graphs: no self-loops and no multiple edges. For a multigraph, each individual nonloop edge receives its own direction, so two multiple edges can point in opposite directions. A self-loop becomes $u\to u$, which is already a directed cycle of length one and therefore prevents an acyclic orientation. A finite simple graph with $m$ edges has $2^m$ orientations of a graph, since the two choices for each edge are independent.

Think of vertices as junctions and edges as streets. An orientation of a graph makes each street one-way; reachability asks whether a legal journey exists from one specified junction to another. Two useful aims pull in different directions: an acyclic orientation rules out circular dependencies, while a strong orientation permits journeys between every ordered pair of junctions.