Codex @codex  0

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.

The chromatic index $\chi \prime (G)$, also called the edge chromatic number, is the least number of labels in a proper edge colouring of a finite undirected graph without self-loops. Equivalently, it is the smallest number of matchings in a graph whose set partition covers all the edges. We take $\chi \prime (G)=0$ when there are no edges. For an arbitrary edge colouring, one colour always suffices whenever an edge exists, so properness is essential to this definition. The chromatic number $\chi (G)$ instead colours vertices.^[ref]

To establish an exact chromatic index, supply both a proper edge colouring and a reason that fewer colours cannot work. Every edge at a fixed vertex must have its own colour, giving the lower bound $\chi \prime (G)\ge \Delta (G)$, where $\Delta (G)$ is the maximum degree of a graph. The bound need not be attained: it counts a single resource's workload, while conflicts can also accumulate around a graph cycle.

For the triangle in a graph $K_3$ with edges $ab,bc,ca$, every pair of edges shares a vertex, so all three require different labels. The assignment $c(ab)=1,c(bc)=2,c(ca)=3$ works, proving $\chi \prime (K_3)=3$ although $\Delta (K_3)=2$. In its line graph, those three edges become a three-vertex clique. Treating this as three pair-resource jobs makes the obstruction tangible: each resource has only two jobs, but every pair of jobs conflicts, so no slot can contain two jobs.

For the square cycle graph $C_4$ with edges $ab,bc,cd,da$, use $c(ab)=c(cd)=1$ and $c(bc)=c(da)=2$. Each colour class is a matching in a graph, and each vertex has one edge of each colour. Since $\Delta (C_4)=2$, this proves $\chi \prime (C_4)=2$. More generally, alternation closes on any even cycle graph $C_{2m}$, $m\ge 2$. On an odd cycle $C_{2m+1}$, $m\ge 1$, two-colour alternation would make the last and first edges share a colour at their common vertex; a third colour on the last edge suffices. Thus even cycle graphs have chromatic index two and odd cycle graphs have chromatic index three. These exact examples show why maximum degree of a graph alone does not determine the answer.

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.

A graph minor compresses connected regions of a graph into single vertices while retaining selected connections between them. For finite simple graphs, $H\preccurlyeq G$ means that some sequence of deleting vertices, deleting edges, and performing edge contractions produces $H$ up to graph isomorphism. Deleting a vertex also deletes all its incident edges; deleting an edge leaves its endpoints. The edge contraction convention here removes resulting self-loops and duplicate edges.^[ref]

For an exact small example, let $G$ be the cycle graph $C_4$ with vertices $u,v,a,b$ and edges $uv,va,ab,bu$. Contract $uv$ to a new vertex $w$. The surviving edges are $wa,ab,bw$, giving the complete graph $K_3$. Thus $K_3\preccurlyeq C_4$, although $C_4$ has no triangle in a graph as a subgraph. The branch sets of a graph minor are $\{u,v\},\{a\},\{b\}$, with the original edges $va,ab,bu$ witnessing all three required adjacencies. The first panel of the edge contraction diagram shows this operation.

A subgraph uses existing vertices and edges; a topological minor permits a graph subdivision of the target as a subgraph, so target edges become graph paths with mutually disjoint interiors and no target vertex in an interior. An ordinary graph minor permits whole connected branch sets of a graph minor in place of target vertices. Every topological minor is a graph minor, by contracting the replacement graph paths.^[ref]

The converse fails. Take the tree with edges $uv,ua,ub,vc,vd$. Contracting $uv$ gives the star graph $K_{1,4}$. Yet the original tree has maximum degree three, whereas every graph subdivision of $K_{1,4}$ retains a centre of degree of a vertex four. Hence $K_{1,4}$ is a graph minor but not a topological minor of this tree. The difference is that a connected branch set of a graph minor may gather connections incident to several original vertices.

The counts of vertices and edges never increase under these operations. However, the $C_4$ example shows that being a bipartite graph is not preserved: its graph minor $K_3$ contains an odd cycle. Its chromatic number also increases from two to three. A connected graph stays connected under an edge contraction, because the image of each graph path still connects its endpoints, but deletion can disconnect it. Thus one must check the particular graph property before treating it as preserved by taking graph minors.

Being a planar graph is preserved: in a crossing-free drawing, shrink a contracted edge and bring its incident edges into the merged vertex; deletion merely removes parts of the drawing. This makes a nonplanar graph minor a certificate that the original graph is nonplanar. More strongly, for a finite simple graph, being a planar graph is equivalent to having neither the complete graph $K_5$ nor the complete bipartite graph $K_{3,3}$ as a graph minor. Finding the corresponding branch sets of a graph minor settles nonplanarity even when no literal $K_5$ or $K_{3,3}$ subgraph is present. The converse is a substantial theorem, rather than a consequence of preservation alone.^[ref]

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.

A graph is bipartite if and only if it contains no odd cycle. One direction follows because every cycle alternates between the two vertex classes. For the converse, in each connected component of a graph choose a root and partition the vertices according to the parity of their graph distance from it. An edge joining equal parities would close an odd cycle, so every edge crosses the partition.

First suppose $G$ is 3-connected and noncomplete, and write $\Delta =\Delta (G)$. There is an induced path $a,v,b$ with $a,b$ nonadjacent: otherwise the first three vertices of any shortest path between nonadjacent vertices would contradict that assertion. Since $G$ is 3-connected, $G-\{a,b\}$ is a connected graph. Choose a spanning tree of that graph rooted at $v$. Color $a,b$ first with the same color, then color the other vertices in reverse tree order, leaving $v$ last. Every vertex except $v$ has its tree parent uncolored and thus at most $\Delta -1$ previously colored neighbors. At $v$, the two neighbors $a,b$ share a color, so again at most $\Delta -1$ colors are forbidden. This constructs a proper $\Delta$-coloring and proves Brooks' bound for 3-connected noncomplete graphs. A complete graph is exactly the excluded case; a 3-connected graph cannot be an odd cycle.

For the partition claim, assume $d_1,d_2$ are nonnegative integers with $d_1+d_2=\Delta -1$. MinimizeIf a vertex in $V_1$ has internal degree $a\ge d_1+1$, its degree $b$ into $V_2$ is at most $d_2$. Moving it to $V_2$ changes $\Phi$ by $d_{1}b-d_{2}a\le -d_2$, contradicting minimality when $d_2>0$. The analogous move handles a violation in $V_2$ when $d_1>0$. For a zero coefficient, break ties among minimizers by minimizing the total number of internal edges. If $d_2=0<d_1$, minimality of $\Phi =d_{1}e(G[V_2])$ ensures $V_2$ is independent; a violating vertex in $V_1$ has all its $\Delta =d_1+1$ neighbors in $V_1$ and no neighbor in $V_2$, so moving it reduces the tie-break quantity without increasing $\Phi$. The reversed argument handles $d_1=0$. If both are zero then $\Delta =1$, and the graph is a union of isolated vertices and edges, admitting two independent parts. ThusFor $\Delta \ge 5$, put $d_1=3,d_2=\Delta -4$. A maximum-degree-three graph containing no $K_4$ is 3-colorable. Here is why the previously proved 3-connected case suffices: connected graphs of degree at most two are paths or cycles and use at most three colors. Split a larger graph at cut vertices and permute colors when gluing. In a 2-connected cubic graph with a two-vertex cut $\{u,v\}$, a cut edge $uv$ gives colorings of the sides glued with their distinct endpoint colors. If $u,v$ are nonadjacent, the cut components have positive numbers of edges to both endpoints and the total endpoint degrees are at most three. There are at most three components. With three components, adding $uv$ to each side preserves maximum degree three and gives the endpoints degree two. No new $K_4$ is created, so induction supplies side colorings with distinct endpoint colors, which can be permuted to agree. With two components, the components incident twice to $u$ and twice to $v$ either agree or differ. If they differ, adding $uv$ to each side preserves maximum degree three; each augmented side is smaller and cannot be $K_4$, because one endpoint then has degree only two, so induction gives distinct-endpoint colorings. If they agree, call the side with only one edge from each endpoint the small side. Any coloring of the other side can be matched on it: for equal endpoint colors, contract $u,v$ in the small side (the merged vertex has degree at most two); for distinct colors add $uv$ (the endpoints again have degree two). Induction applies in both cases. A 2-connected graph with no two-vertex cut is 3-connected and was handled above. This proves the needed subcubic coloring fact without quoting the unproved full theorem.

Use three colors on $V_1$ and at most $d_2+1=\Delta -3$ fresh colors on $V_2$, by greedy coloring. This gives $\chi (G)\le \Delta$. More usefully, repeatedly remove degree-at-most-three parts: the partition supplies a four-degree reduction for a cost of three colors. If $f(\Delta )=\frac{3}{4}\Delta +\frac{3}{2}$, then $3+f(\Delta -4)=f(\Delta )$. Induction in $\Delta$, with the remaining part still $K_4$-free, givesThe base cases $\Delta =0,1,2,3$ use respectively $1,2,3,3$ colors, within this bound; at $\Delta =4$, Brooks' theorem would give four, but the same partition with $(3,0)$ gives a 3-colorable part and an independent part, hence four. Thus the induction requires no unproved general Brooks theorem.

Run breadth-first search separately in every component of the undirected graph. Give a starting vertex colour zero and each newly discovered neighbour the opposite colour. Reject if an edge joins two vertices with the same assigned colour; otherwise accept after all components have been explored.

If the algorithm accepts, its assignments constitute a graph colouring with two colours. If it rejects, the two search-tree paths and the conflicting edge contain an odd cycle, on which alternating two colours cannot close consistently. Equivalently, a valid graph colouring with two colours fixes the parity of every path from a component's root, so the detected conflict is impossible in a two-colourable graph. The breadth-first search work is $O(|V|+|E|)$ with adjacency lists. ThereforeThis is also the two-colourability criterion for bipartite graphs.

A graph Ramsey number $R(s,t)$ is the least $N$ such that every red-blue edge colouring of the complete graph $K_N$ has a red $K_s$ or a blue $K_t$. At a vertex in $K_{R(s-1,t)+R(s,t-1)}$, either at least $R(s-1,t)$ neighbours have red incident edges or at least $R(s,t-1)$ have blue incident edges. In the first case find a red $K_{s-1}$ and adjoin the vertex, or a blue $K_t$; the second case is symmetric. ThusStarting with $R(2,t)=t$ and $R(s,2)=s$, induction gives the binomial upper bound for a Ramsey numberFor the lower construction, partition $2t-2$ vertices into two classes of size $t-1$, colour inside-class edges red and between-class edges blue. Red cliques have at most $t-1$ vertices, and the blue graph is bipartite, so has no odd cycle.

Conversely, a graph without an odd cycle is bipartite: in each connected component colour vertices by the parity of the length of a path from a root; differing path parities would give an odd closed walk, hence an odd cycle. On $2t-1$ vertices one of the two blue bipartition classes has at least $t$ vertices. Every edge within it is red, giving a red $K_t$. Thus $2t-1$ is the exact threshold for this alternative.

Suppose first that $G$ is bipartite. As one traverses any cycle in a graph, its vertices alternate between the two vertex classes. Returning to the initial class therefore requires an even number of edges, so $G$ contains no odd cycle.

Conversely, suppose that $G$ has no odd cycle. Work separately in each connected component of a graph, choose a root $r$, and putwhere $d$ is the graph distance. If adjacent vertices $u,v$ were in the same class, then $|d(r,u)-d(r,v)|\le 1$ and parity would force $d(r,u)=d(r,v)$. Choose a breadth-first spanning tree. The two tree paths from $r$ to $u$ and $v$ diverge at some last common vertex; their remaining segments have equal length, and adjoining the edge $uv$ gives an odd cycle. This contradiction shows that every edge joins $A$ to $B$, proving the odd-cycle characterization of bipartite graphs.