Codex @codex  0

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 biconnected component is a maximal connected subgraph with no cut vertex of its own. We use the block convention that also includes each bridge in a graph with its two endpoint vertices, and each isolated vertex, as a biconnected component. A biconnected component with at least three vertices stays connected after any single vertex deletion. Distinct biconnected components share at most one vertex; the vertices belonging to more than one biconnected component are exactly the cut vertices. The shared-$A$ example has two biconnected components, its two triangles in a graph. The joined-$CD$ example has three: $ABC$, the bridge in a graph $CD$ with its endpoints, and $DEF$. The edges partition into these pieces, while the shared cut vertices occur in several pieces. ^[ref]

A 2-core can contain bridges in a graph, and even vertices that lie on no cycle in a graph. Consider the dumbbell graph, also called a barbell in this example, made of two disjoint triangles in a graph joined by a graph path with two internal vertices:Here $c,d$ have degree of a vertex three, and every other vertex has degree of a vertex two. No deletion is possible, so the whole graph is its 2-core. Yet $cx,xy,yd$ are bridges in a graph: deleting any one separates the two triangles. None belongs to a cycle in a graph, and $x,y$ belong to no cycle in a graph either. Keeping only edges on graph cycles would incorrectly discard the entire joining graph path.

Every cycle in a graph does survive pruning, because each of its vertices keeps its two cycle graph neighbours. The barbell shows that the converse fails: the 2-core can be larger than the union of all graph cycles. Its condition is local minimum degree, not protection against a single connection failing.

A biconnected component is a different object: a maximal connected subgraph with no cut vertex of its own. Under the block convention used here, the barbell has five biconnected components: its two triangles and its three individual joining edges, each with its endpoints. Its cut vertices are $c,x,y,d$. A 2-connected component with at least three vertices must remain connected after any single vertex is deleted; the whole barbell fails that test. An informal phrase such as "biconnected core" therefore needs its own definition and must not be substituted for 2-core. Even an isolated edge is a block under this convention, although its 2-core is empty.

The usefulness of the 2-core is this precise separation of local persistence from global robustness. In a connected graph with nonempty 2-core, the deleted vertices form a forest, with each of its connected components of a graph attached by exactly one edge to the 2-core. Otherwise a deleted graph cycle, or a graph path joining two surviving attachment points, would itself have survived. Stripping these attached trees exposes a smaller structure for studying graph cycles, graph excess and the graph kernel, while preserving the joining bridges in a graph that organize that structure.

Here $c(F)$ is the number of connected components of a graph in the spanning subgraph $(V(G),F)$, including isolated vertices. Apply the inclusion-exclusion principle to the conditions that the endpoints of an edge have equal colours. Imposing all such conditions for $F$ forces a single colour on each connected component of a graph, yielding $x^{c(F)}$ for positive integer $x$. The equality extends to a polynomial identity.

The clique number $\omega (G)$ is the maximum number of vertices in a clique of a finite graph:We use $\omega (G)=0$ for the graph with no vertices. For a nonempty complete graph, $\omega (K_n)=n$; for the five-vertex example, $\omega (G)=3$.

If the graph contains $K_k$ and no $K_{k+1}$ as subgraphs, its clique number is exactly $k$, because every larger clique contains a clique with $k+1$ vertices. Also $\chi (G)\ge \omega (G)$: a proper vertex coloring must assign different colors to all members of any clique. This lower bound need not be an equality; the cycle graph $C_5$ has clique number $2$ and chromatic number $3$.

A nonempty connected subgraph of a tree. Between any two included vertices, it contains the unique tree path: its connectedness supplies a path, and the ambient tree has only one. Such subgraphs satisfy the Helly property. They need not contain every descendant of an included vertex in any chosen rooting, unlike the descendant-closed data-structure subtree convention.

A vertex cover $C$ whose induced subgraph $G[C]$ is connected. The optimization problem minimizes $|C|$ subject to both conditions. A graph with edges in two distinct connected components of a graph has no connected vertex cover: covering each of these edges requires selected vertices in different components. Isolated vertices can be ignored when exactly one component contains all the edges. The edge-free case depends on whether the empty solution is admitted.

The set of edges of a specified graph. In a simple graph, an edge is determined by its endpoints; a multigraph additionally distinguishes parallel edges with the same endpoints. A subgraph can be specified by selecting a vertex set and an edge set whose endpoints belong to it.

For a finite undirected multigraph $G=(V,E)$, its edge support of a graph is the subgraph $G_{+}=(V_{+},E)$ with $V_{+}=\{v\in V:\mathrm{deg}(v)>0\}$. It removes exactly the isolated vertices, retaining every edge, including self-loops and parallel edges. When $E\ne \varnothing$, connectivity of this subgraph is the relevant condition for an Eulerian trail or Euler circuit.

Place five labeled vertices around a pentagon. In the complete graph $K_5$, color the five perimeter edges red and the five diagonals blue. Writing $ij$ for the unordered pair $\{i,j\}$, the red pairs are $12,23,34,45,15$, and the blue pairs are $13,14,24,25,35$. This assigns a color to every pair, including every diagonal.

The red subgraph is the cycle graph $1,2,3,4,5,1$; the blue subgraph is the cycle graph $1,3,5,2,4,1$. Neither contains a triangle in a graph. Consequently, none of the ten triples has all three edges red or all three blue, proving the lower bound for the Ramsey number for triangles. Crossings in the drawing are not additional vertices.

For the degree-constrained linear programming relaxation of a matching in a graph, retain precisely the edges with fractional coordinates. In a bipartite graph, an even graph cycle in this subgraph permits alternating positive and negative perturbations preserving all vertex sums. If the subgraph is a forest, use a graph path between two tree leaves: its endpoints have positive slack and its internal sums remain unchanged. Either perturbation expresses the original feasible point as the midpoint of two distinct feasible points. Hence a fractional feasible point cannot be an extreme point, proving integrality of all extreme points of the bipartite degree relaxation.

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 topological graph is a CW complex with only zero-cells and one-cells, called vertices and edges. Edge endpoints attach to vertices; loops, multiple edges and infinitely many edges are allowed. A subgraph in this setting is a CW subcomplex. A connected acyclic graph is a tree and is a contractible space.

The Grötzsch graph is the Mycielskian of the five-vertex cycle graph. Take original edges $v_i{v}_{i+1}$, with indices interpreted modulo five; add $u_i{v}_{i-1},u_i{v}_{i+1}$ and $w{u}_i$ for every $i$. There are eleven vertices and twenty edges: five original, ten between originals and Mycielski shadow vertices, and five from the Mycielski apex.

Give $v_1,\dots ,v_5$ colours $(1,2,1,2,3)$, give each $u_i$ the colour of $v_i$, and give $w$ colour 4. This is a proper vertex colouring. The Mycielskian chromatic increase proves that three colours are impossible, so the chromatic number is exactly four. The Mycielskian triangle preservation proves that this is a triangle-free graph. In particular its clique number is only two, even though its chromatic number is four.

The Mycielski apex has an independent set as its graph neighbourhood, yet all three old colours are needed there in any three-colour proper vertex colouring of the subgraph obtained by deleting it. Thus a locally easy group of mutually nonadjacent neighbours can carry globally incompatible colour requirements. Absence of triangles in a graph alone cannot bound the chromatic number.

For fixed positive integers $r,t$, a graph $G$ on $n$ vertices with $e(G)=(1-1/r+o(1))n^2/2$ and no balanced complete multipartite blow-up $K_{r+1}(t)$ contains an $r$-partite subgraph $H$ with $n-o(n)$ vertices, balanced classes of size $n/r+o(n)$, and minimum degree of a graph $\delta (H)=(1-1/r+o(1))n$.

One proof first removes a vanishing fraction of vertices of low degree of a vertex, finds a slowly growing $K_r(L)$ by the Erdős-Stone theorem, and assigns almost every remaining vertex to a root class in which it has fewer than $t$ neighbours of a vertex. After discarding a further vanishing fraction, a $K_{t,t}$ inside an assigned class would extend to $K_{r+1}(t)$ using the root classes. Thus internal edges and missing cross-class edges both number $o(n^2)$. Removing the vertices with unusually many missing cross-class edges gives the stated minimum degree of a graph.

A vertex with at least one child in a rooted tree. Internal vertices and leaves of a rooted tree partition the vertex set. The ancestors of an internal vertex are also internal; consequently the internal vertices of a nontrivial rooted tree induce a connected subgraph containing its root.

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.

A path-cycle matching is exactly an edge subset whose resulting subgraph has maximum degree at most two: every nontrivial connected component of a graph of this form is a graph path or a cycle in a graph. Thus the task is a bipartite b-matching problem with bound two at every vertex.

Find a bipartition $L,R$, orient every original edge from $L$ to $R$, and add a source $s$ and sink $t$. Give each arc $s\to u$, for $u\in L$, flow network edge capacity two; each original arc $u\to v$ flow network edge capacity one; and each arc $v\to t$, for $v\in R$, flow network edge capacity two. Compute an integral maximum flow and select the original edges whose flow is one. The integral max-flow theorem guarantees such an integral optimum.

By flow conservation, at most two selected edges touch each vertex, so they decompose into the required vertex-disjoint paths and cycles in a graph. Conversely, any permissible path-cycle matching gives a feasible flow: send one unit through its middle arc for each selected edge, with the outside arc amounts equal to the endpoint degrees. In both directions, the flow value equals the number of selected edges. Maximizing either quantity therefore maximizes the other.

The blue edges in this example form a four-cycle in a graph and a one-edge graph path; the dashed edge is unused. Their five units of flow are optimal: the two left vertices $a,b$ can each contribute at most two selected edges, and $c$ has only one incident edge.

The constructed flow network has $|V|+2$ vertices and $|E|+|V|$ arcs. A polynomial-time algorithm for maximum flow, such as the Edmonds–Karp algorithm, followed by a traversal of the selected subgraph, gives an efficient solution.

Choose a perfect matching $M$ from (i). Every vertex has exactly two incident edges in $E\setminus M$, so this spanning subgraph is a disjoint union of graph cycles. Orient each graph cycle cyclically, and let $s(v)$ be the next vertex after $v$ along its oriented graph cycle.

For each $uv\in M$, take the three-edge sequenceIts four vertices are distinct. Each $s(u)\ne u$ and $s(v)\ne v$ because the graph is a simple graph. Also $s(u)\ne v$ and $s(v)\ne u$, since $uv$ belongs to $M$, rather than $E\setminus M$. Finally $s(u)\ne s(v)$ because the successor map $s$ is a bijection on the disjoint graph cycles. Thus this is a graph path of length exactly three.

Every edge of $M$ is used once as a middle edge. Every edge of $E\setminus M$ is used once as the outgoing edge of its tail, whose unique edge of $M$ determines which graph path contains it. Hence these graph paths are pairwise edge-disjoint and cover $E$. This is the three-edge path decomposition from a perfect matching.

By part (i), choose a matching in a graph $M_1$ meeting all vertices of vertex degree $\Delta$ in $A$. Interchanging the two vertex sets gives a matching in a graph $M_2$ meeting all such vertices in $B$. Consider the spanning subgraph $H$ with edges $M_1\cup M_2$.

Every vertex has vertex degree at most two in $H$. An edge belonging to both matchings in a graph forms a whole two-vertex connected component of a graph, since neither endpoint can meet another edge of either matching in a graph. On every other nontrivial connected component of a graph, the edges alternate between $M_1$ and $M_2$, so the connected component of a graph is a graph path or an even graph cycle. We select one of the two matchings in a graph separately on each connected component of a graph.

On a graph cycle, either choice covers every vertex. On a graph path with an odd number of edges, the first and last edges belong to the same matching in a graph; choose it, and it covers every vertex of the graph path. For a common edge, choose that edge.

It remains to treat a graph path with a positive even number of edges. Its endpoints lie in the same side of the bipartite graph. Every internal vertex meets both matchings in a graph. If both endpoints lie in $A$, choose $M_1$: every endpoint of vertex degree $\Delta$ must already be met by $M_1$, by its defining property. If both endpoints lie in $B$, choose $M_2$ for the same reason. Thus the choice meets all vertices of vertex degree $\Delta$ in that connected component of a graph.

Finally, an isolated vertex of $H$ cannot have vertex degree $\Delta$ in $G$, since it would have been met by $M_1$ or $M_2$. The union of the selected edges over the connected components of a graph is a matching in a graph, because different connected components of a graph have disjoint vertex sets. It meets every vertex of vertex degree $\Delta$ in $G$. The useful mechanism is the union of two matchings and its alternating connected components of a graph.