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.

A graph is connected when every pair of vertices is joined by a path.

An edge contraction merges the two endpoints of an existing edge. For a finite simple graph $G$ and $e=uv$, replace $u,v$ by a new vertex $w$. Retain every edge with neither endpoint in $\{u,v\}$, and join $w$ to every member ofHere $N_G(u)$ and $N_G(v)$ denote the original open graph neighbourhoods, and $N_{G/e}(w)$ is the new graph neighbourhood. Remove the self-loop arising from $uv$ and merge duplicate edges, so the result $G/e$ is again a simple graph. This is not deletion of $uv$, which keeps both original vertices.^[ref]

The left example contracts $uv$ in the cycle graph $C_4$ to give $\{wa,ab,bw\}$. Its endpoints have no common neighbours, so four edges become three. The right example contracts $uv$ in the triangle in a graph with edges $uv,ua,va$. Its endpoints have the single common neighbour $a$, so the two edges $ua,va$ become one edge $wa$: three edges become one.

For any such edge contraction, the exact counts areThe contracted edge accounts for one loss. Each common neighbour $z$ contributes exactly one further loss, since $uz,vz$ become a single edge $wz$. All other edges correspond one-to-one to surviving edges. In particular the new degree of a vertex isThese formulas depend on simplifying to a simple graph; a multigraph convention that retains duplicate edges has different counts. In the six-vertex branch set of a graph minor diagram, contracting $12$ loses one edge, contracting the resulting $34$ loses two because of its common neighbour $A$, and contracting $56$ loses one. Hence its seven edges become the three edges of $K_3$: $7-1-2-1=3$.

An edge contraction can increase a degree of a vertex even while decreasing both total counts. For example, contracting $uv$ in the tree with edges $uv,ua,ub,vc,vd$ merges two vertices of degree of a vertex three into one of degree of a vertex four. This is the mechanism behind the distinction between a graph minor and a topological minor.

A graph describes objects, called vertices, and pairwise connections, called edges. Its vertex set $V$ tells us what the objects are; $E$ records their connections. The basic abstraction retains graph adjacency while discarding positions, angles and Euclidean distances: moving the dots in a drawing changes none of the edges. A crossing of two drawn lines is not an extra vertex unless explicitly designated as one. Even the labels can change: a graph isomorphism is a relabelling that preserves graph adjacency in both directions.^[ref]

This makes graphs useful when the question concerns possible connections rather than physical shape. For example, model locations by vertices and direct links by edges; a graph path answers whether one location can reach another. Alternatively, let vertices be activities and edges represent conflicts: a graph coloring then assigns compatible time slots. These are mathematical models, so one must decide which pairwise relationship an edge means before applying graph theory.^[ref]

Our running simple graph haswhere $AB$ abbreviates the unordered pair $\{A,B\}$. It consists of two triangles in a graph, $ABC$ and $DEF$, joined by $CD$. The two drawings above have identical graph adjacency, even though their apparent lengths differ. What counts is that $C$ and $D$ are adjacent, whereas $A$ and $F$ are not.

Route questions require precise vocabulary. A walk is a sequence of consecutive adjacent vertices, permitting repetitions; its length counts traversed edges. A trail is a walk that repeats no edge; a graph path repeats no vertex. For a multigraph, the walk must also specify which parallel edge each step uses. For instance, $A,B,A,C,D,F$ is a length-five walk but not a trail, since it uses $AB$ twice. The length-three graph path $A,C,D,F$ is a shortest route: crossing between the two triangles in a graph requires $CD$, with at least one edge before it and one after it. Thus $d(A,F)=3$ in graph distance, regardless of the drawing.^[ref]

An Eulerian trail uses every edge exactly once, allowing repeated vertices; a Hamiltonian path visits every vertex exactly once, without needing every edge. Here $C,A,B,C,D,E,F,D$ is an Eulerian trail of length seven, whereas $A,B,C,D,E,F$ is a Hamiltonian path of length five. The first repeats $C,D$; the second omits $AC,DF$. Calling an Eulerian trail an "Eulerian path" must not be taken to impose our graph path convention.^[ref]

The classic historical example is Euler's Königsberg bridge problem: represent the four land regions by vertices and the seven bridges by distinct edges, giving a multigraph. Their degrees of vertices are $3,3,3,5$. In a trail using every edge, arrivals and departures pair at every internal vertex, so at most the two endpoints can have odd vertex degree. Four odd degrees of vertices therefore rule out such a route. This early foundational example of graph theory needs neither bridge lengths nor a geographical map. Euler's paper is conventionally associated with 1736, the volume's nominal year; the Euler Archive records its writing in 1735 and publication in 1741.^[ref][ref]

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]

A graph subdivision $TH$ replaces each edge $uv$ of a simple graph $H$ by a graph path of at least one edge joining its original endpoints. The original vertices are branch vertices of a graph subdivision. The replacement graph paths have pairwise disjoint interiors, contain no branch vertices of a graph subdivision internally, and together make up the entire new graph. Leaving an edge unchanged is allowed.^[ref]

For an explicit example, take $H$ with vertex set $\{A,B,C,D\}$ and edges $AB,BC,CA,AD$: a triangle in a graph with one attached leaf of a graph. Replace its edges by the following branch paths of a graph subdivision:The resulting graph subdivision $S$ has vertex set $\{A,B,C,D,x,y,z\}$ and edges $Ax,xB,By,yz,zC,CA,AD$. The internal vertex sets are $\{x\},\{y,z\},\varnothing ,\varnothing$, so disjointness is explicit. The degrees of vertices of $A,B,C,D$ remain $3,2,2,1$, respectively; the three new internal vertices each have degree of a vertex two.

Adding $m$ internal vertices to a finite graph increases both its vertex count and its edge count by $m$. Here $m=3$, so four vertices and four edges become seven of each; the graph excess is unchanged. Each replacement graph path remains a route between the same junctions. Thus graph subdivision preserves whether a graph is a planar graph: insert intermediate vertices along a crossing-free drawing, or trace each replacement graph path as one edge to recover a drawing of the original graph. Travel times or capacities are separate modelling choices and are not determined by this adjacency construction.

A topological minor records a network pattern whose vertices remain individual junctions but whose edges may become longer routes. For finite simple graphs, $H{\preccurlyeq }_{\mathrm{top}}G$ means that $G$ contains a subgraph that is a graph subdivision of $H$ up to graph isomorphism. Equivalently, choose distinct branch vertices of a graph subdivision $b_v\in V(G)$ for $v\in V(H)$ and a graph path $P_{uv}$ from $b_u$ to $b_v$ for every $uv\in E(H)$. These are internally vertex-disjoint paths, and no internal vertex of any $P_{uv}$ is a branch vertex of a graph subdivision. Only endpoints corresponding to a shared target vertex may be shared.^[ref]

The graph subdivision example below replaces two edges of a triangle in a graph by routes of two and three edges while retaining its attached leaf of a graph. If the host graph also contains an extra edge $BD$, the same routes still witness a topological minor: delete $BD$ when selecting the subgraph. An induced subgraph is not required. However, routes that merely connect the right pairs are insufficient: using a branch vertex of a graph subdivision as an intermediate junction, or making two routes share an internal vertex, can change the local network structure.

Every topological minor is a graph minor. In each branch path of a graph subdivision, contract all but one edge; the disjoint interiors let this shorten each route without merging distinct branch vertices of a graph subdivision. This recovers $H$ after deleting unused vertices and edges.^[ref] The converse fails because an ordinary branch set of a graph minor can gather several junctions into one.

For the tree $T$ with vertices $u,v,a,b,c,d$ and edges $uv,ua,ub,vc,vd$, contracting $uv$ produces a star graph $K_{1,4}$: the branch sets of a graph minor are $\{u,v\},\{a\},\{b\},\{c\},\{d\}$. Both $u,v$ have degree of a vertex three; each of the other four vertices is a leaf of a graph with degree of a vertex one. The new centre $w$ has four distinct graph neighbours $a,b,c,d$; its degree of a vertex is $3+3-2=4$, in agreement with the edge contraction formula.

Yet $K_{1,4}$ is not a topological minor of $T$. In a graph subdivision of $K_{1,4}$, four branch paths of a graph subdivision must leave the centre through four different edges; sharing their first internal vertex would violate internal disjointness. Thus any host needs a vertex of degree of a vertex at least four, whereas $\Delta (T)=3$. More generally, $H{\preccurlyeq }_{\mathrm{top}}G$ implies $\Delta (H)\le \Delta (G)$, where $\Delta$ is the maximum degree of a graph. This bound concerns the host graph; extra unused edges may make its branch vertices of a graph subdivision have larger degrees of vertices than their target counterparts.

This distinction matters when a network's individual junctions have a limited number of connections: replacing a connection by a route preserves the number of routes meeting at each chosen junction, while contracting a connected region can combine connections from separate junctions. It also explains why a small nonplanar pattern can hide inside long routes. By Kuratowski's theorem, a finite simple graph is a planar graph exactly when it has neither the complete graph $K_5$ nor the complete bipartite graph $K_{3,3}$ as a topological minor. The obstruction is a graph subdivision inside the network, regardless of the number of intermediate vertices.