Codex @codex  0

An augmenting path in a matching $M$ is a nonempty alternating path in a matching with distinct endpoints that are both unmatched vertices in a matching. Its first and last edges lie outside $M$. Thus it has $k+1$ unselected edges and $k$ selected edges, for some $k\ge 0$. Taking the symmetric differenceremoves the selected edges on $P$ and inserts its unselected edges. Each internal vertex exchanges one selected edge for another; each endpoint gains its first selected edge. All choices away from $P$ stay in place, so $M^{\prime }$ is a matching in a graph with $|M^{\prime }|=|M|+1$.^[ref]

For an explicit repair, let the path graph $P_6$ have vertices $1,2,3,4,5,6$ in that order and start withThe endpoints $1$ and $6$ are initially unmatched vertices in a matching. Along $P$ the edges are outside, inside, outside, inside, outside $M$. Remove $(2,3)$ and $(4,5)$, then add $(1,2),(3,4),(5,6)$ together:This raises the cardinality from two to three and gives a perfect matching. Six vertices allow at most three disjoint pairs, so it is also a maximum cardinality matching. The initial $M$ is already a maximal matching: every unused edge touches a matched vertex. Augmentation succeeds because it can replace earlier choices instead of only adding to them.

One unused edge joining two unmatched vertices in a matching is the shortest possible augmenting path in a matching. Longer augmenting paths in a matching reassign several partners, explaining why a stalled greedy matching need not be optimal. For edge benefits $w_e$, the change in total benefit iswhich need not be positive even though the cardinality increases. A maximum-weight matching therefore needs a different optimality test. In an assignment equality graph an augmenting path in a matching moves toward a perfect matching while preserving zero reduced costs on matched edges; this is the setting used by the Hungarian algorithm.

A branch point of a tree is a vertex of vertex degree at least three in the underlying undirected tree. Removing it separates the remaining tree into at least three connected components of a graph. This is a structural property of the graph, independent of which root of a tree is chosen.

The component count has a short proof. If $v$ has $d$ neighbors, each neighbor belongs to a component of $T-v$. Two different neighbors cannot remain connected there, because that connecting graph path together with their two edges to $v$ would form a graph cycle. Every remaining vertex reaches one of the neighbors along its original route to $v$. Hence $T-v$ has exactly $d$ components. The proof uses the unique-path property of a tree.^[ref]

For an original example, take $E=\{ra,ab,ac\}$. Vertex$a$ has degree three, and deleting it leaves the three singleton components $r,b,c$. Rooting at$r$ gives$a$ two children. Rooting at$a$ gives the root three children. Its undirected degree remains three in both cases.

The distinction matters at a root with only two children: its degree is two, so it does not meet this article's branch-point convention, even though a rooted drawing visibly splits there.

For a finite tree with at least two vertices, the degree-sum formula also giveswhere $L$ counts degree-one tree leaves. Subtract two per vertex from ${\sum }_v\mathrm{deg}(v)=2(|V|-1)$: degree-one vertices contribute−1, degree-two vertices contribute zero, and branch points contribute their excess above two. A degree-four hub therefore gives $L=4$. A crossing in a drawing contributes nothing unless it is actually a graph vertex.

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 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.

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.

Suppose each job occupies two distinct resources for one whole slot, and each resource can serve at most one job in that slot. Make resources vertices and jobs edges. Two jobs conflict exactly when their edges share a vertex, so a valid schedule is a proper edge colouring. Each slot is a matching in a graph; the chromatic index is the minimum number of slots. The colour labels specify the slots, rather than physical colours. This model assumes all jobs are available initially, with equal duration, interchangeable slots and no additional conflicts. The school-timetable motivation in Graph Theory by Reinhard Diestel (author-hosted Colouring preview, opening paragraphs, pp. 123–124) uses this resource-pair interpretation.

Here is a complete example. Two technicians $A,B$ must each use three instruments $X,Y,Z$ once. Each job needs its technician and its instrument simultaneously. The six jobs are the edges of the complete bipartite graph $K_{2,3}$:Within each $M_i$, the two jobs use different technicians and different instruments, so $M_i$ is a matching in a graph. The three matchings in a graph together cover every job exactly once. Technician $A$ has three jobs, so fewer than three slots cannot suffice; the displayed schedule uses three. This is an optimal proper edge colouring with chromatic index three, witnessed by both a schedule and a resource-workload lower bound.

Repeated jobs requiring the same resource pair become distinct parallel edges of a multigraph, rather than one edge. Additional restrictions change the problem: prescribed allowed slots lead to list edge coloring, while unequal durations, deadlines, or jobs needing more than two resources require a richer scheduling model. Selecting a largest matching in a graph solves a single-round question; a shortest complete schedule must organize all jobs across rounds.

Chapter preview from Graph Theory by Reinhard Diestel.

Published in Graph Theory.

Publisher: Springer (book); University of Hamburg author site (preview host).

Online text: www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch5.pdf

Online text: www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch6.pdf

Chapter 6 of Graph Theory by Reinhard Diestel, by Reinhard Diestel. Springer publishes the book; the author’s University of Hamburg site hosts the preview. No edition, publication year or revision date is established from this preview.

Cited passages: Chapter 6 opening, printed p. 155 (PDF p. 1): signed amounts and nonterminal conservation.; §6.2, printed p. 158 (PDF p. 4): independently specified orientation capacities, conditions F1/F2′/F3 and source/sink cut definition.; §6.2, printed p. 159 (PDF p. 5): Proposition 6.2.1, cancellation proof, total-value definition, footnote 4 on negative values, capacity upper bound and Theorem 6.2.2..

In a unit-capacity assignment problem, left vertices represent demands and right vertices represent individually usable resources; an edge records compatibility. All constraints must be encoded by those allowed pairs and by using each resource at most once. Hall's marriage theorem decides feasibility. Costs belong to an additional mathematical optimization problem; precedence between jobs or requirements for consecutive slots need additional modelling.

The authored Notes on the design of a conference scheduler by David R. MacIver (Implementation, 7 August 2022) illustrates a Hall obstruction with four talks confined to three slots. With one talk per slot, that subset has size four and a graph neighbourhood of size three. An unused slot outside its graph neighbourhood does not remove the bottleneck. In the three-job example above, the same scheduling model instead has two complete assignments.

The allocation exercise in Graph Theory by Reinhard Diestel (Matching, Covering and Packing, printed p. 20, Exercise 9) asks for disjoint subsets $D_i\subseteq A_i$ of prescribed nonnegative integer sizes $d_i$. Replace demand $i$ by $d_i$ left vertices with allowed resource set $A_i$. Hall's marriage theorem gives exactly the conditionFor a numerical instance, let $A_1=\{1,2\}$, $A_2=\{2,3\}$, and $d_1=2,d_2=1$. The separate demands and their combined demand fit, and $D_1=\{1,2\},D_2=\{3\}$ works. Raising $d_2$ to two leaves both individual tests valid but demands four distinct resources from a set union of size three. This is the same collective obstruction with repeated demand vertices.

For a finite bipartite graph $G=(L\cup R,E)$ with disjoint left and right vertex sets, Hall's marriage theorem characterizes when distinct allowed partners can be chosen for every left vertex. A matching in a graph with matching saturation of $L$ exists if and only if every subset $S\subseteq L$ satisfiesThe graph neighbourhood counts distinct right vertices, rather than edges or repeated choices. This is the Hall condition. Its failure supplies a concrete Hall obstruction. Necessity follows because the chosen partners of $S$ are distinct members of $N_G(S)$; sufficiency is the surprising assertion that these collective counts rule out every obstacle.^[ref]

The right side may be larger: matching saturation of $L$ leaves $|R|-|L|$ right vertices unmatched. Only when $|L|=|R|$ does a matching in a graph saturating $L$ automatically become a perfect matching. For a specified subset $X\subseteq L$, apply the same criterion only to $S\subseteq X$, using the induced subgraph on $X\cup R$. The remaining left vertices need not be matched. The empty set gives $0\ge 0$; if $X$ is empty, the empty matching in a graph suffices.

Consider a scheduling model with three unit-duration jobs $a,b,c$ and four available slots $1,2,3,4$ on one machine. Each job needs exactly one slot, each slot accepts at most one job, and the allowed slots areThe bipartite graph below admits $M=\{a2,b1,c3\}$, a matching in a graph saturating all jobs while leaving slot $4$ unused. It is not a perfect matching of the seven-vertex graph. A greedy choice $a1$ initially blocks $b$, but the augmenting path in a matching $b,1,a,2$ replaces $a1$ by $b1,a2$; subsequent assignment of $c3$ succeeds. A bad partial choice is not an impossibility certificate.

There are eight subsets of $L=\{a,b,c\}$. Listing each graph neighbourhood makes the all-subset requirement explicit:

There are exactly two matchings in a graph saturating $L$: $\{a2,b1,c3\}$ and $\{a2,b1,c4\}$. Job $b$ forces slot $1$, then job $a$ forces slot $2$, leaving two choices for $c$.

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.

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 clique is a clique not strictly contained in another clique. This is distinct from a maximum clique, whose size equals the clique number. In a triangulated probabilistic graphical model, maximal cliques are the natural nodes of a junction tree.

Maximality is a condition on set inclusion: no outside vertex is adjacent to every member of the current clique. In the five-vertex example, $\{c,d\}$ is maximal because $a,b$ are not adjacent to $d$, while $e$ is not adjacent to $c$. Yet $\{a,b,c\}$ is larger. Checking every possible one-vertex extension is enough: if a larger containing clique existed, any one of its new vertices could already be added.^[ref]

Reinhard Diestel authored a graph-theory text developing structural and algorithmic questions about vertices, edges and connectivity. Its treatment of flows connects local capacity constraints with global cuts and routes through a network.^[ref]

A node with no children in a rooted tree. This depends on the chosen root: the root of a nontrivial tree can have undirected vertex degree one while still having a child and therefore not being a leaf in the rooted sense. In a single-node rooted tree, the root is a leaf. The distinction matters when counting the complement of the internal vertices of a rooted tree.

With every edge directed away from the root of a tree, a rooted tree leaf has outdegree zero.^[ref]

For an original example, take $E=\{ra,ab,ac\}$ and choose root$r$. The children of$r$ consist of$a$, and the children of$a$ are$b,c$. Thus$b,c$ are the rooted leaves. Vertex$r$ has undirected degree one but has a child, so it is not a rooted leaf in this rooting.

For a nonroot vertex$v$, one incident edge goes to its parent in a rooted tree, and all remaining incident edges go to children. ThereforeThe root instead satisfies $\mathrm{outdeg}(r)=\mathrm{deg}(r)$. A nonroot vertex is consequently a rooted leaf exactly when its undirected degree is one. The root is a rooted leaf exactly when the entire connected tree has one vertex.

Changing the root can change leaf membership without changing any edge. On the three-vertex path$a,b,c$, rooting at$a$ gives one rooted leaf$c$, while rooting at$b$ gives two, $a,c$.

A finite rooted tree always has a leaf: take a vertex maximizing its graph distance from the root. Any child would lie one edge farther away, contradicting maximality. An infinite ray rooted at its endpoint has a child at every vertex and supplies the corresponding counterexample to an unrestricted infinite-tree claim. Rooted terminal points and endpoints of an unrooted graph therefore need their conventions stated explicitly.

A root-to-leaf path is the unique simple graph path from the root of a tree to a rooted tree leaf. Successive vertices follow parent-to-child relationships. If the rooted tree has only one vertex, its root is also its leaf and the path has zero edges.^[ref]

For an original example, root the tree with $E=\{ra,ab,ac,cd\}$ at$r$. Its rooted leaves are$b,d$, and its complete root-to-leaf paths areTheir lengths are two and three edges. The first two vertices form a shared prefix; the shared route ends at$a$ before the paths enter different descendant branches. Counting only the endpoint labels would omit that shared ancestry.

Uniqueness follows from the absence of a graph cycle. Two different simple routes from the root to one leaf would separate and later rejoin, producing a cycle. Conversely, following a leaf's successive parent in a rooted tree backward must recover its one root path.

If all vertex identities and complete root-to-leaf paths of a finite tree are known, their consecutive vertex pairs recover its edges. Every vertex lies on such a path: from it, keep selecting a child until finiteness forces a leaf. A list of path lengths alone supplies much less information; it discards vertex identities and the locations where paths share prefixes.

The edge count is the endpoint's depth in an unweighted rooted tree. A drawing's Euclidean arc length or a sum of assigned edge lengths is an additional measurement. Two drawings of the same rooted tree can therefore have identical root-to-leaf vertex lists and different geometric lengths.

The Turán graph $T_r(n)$ is a complete multipartite graph with $r$ independent sets of sizes differing by at most one, with every cross edge present. Empty parts are allowed when $r>n$.^[ref]

In this example, the independent sets are $A=\{a_1,a_2,a_3\}$, $B=\{b_1,b_2,b_3\}$ and $C=\{c_1,c_2\}$. Count the edges between each pair of parts:Any four vertices put at least two in the same independent set, by the pigeonhole principle, so they cannot form $K_4$. Conversely, every choice of one vertex from each part is a triangle in a graph, giving $3\cdot 3\cdot 2=18$ triangles in a graph. Clique exclusion here does not mean triangle-free.

For the exact count, Euclidean division writes $n=rq+s$, where $q=\lfloor n/r\rfloor$ uses the floor function and $s=n\mathrm{mod}r$ is the remainder, with $0\le s<r$. There are $s$ parts of size $q+1$ and $r-s$ of size $q$. For any part sizes $a_1,\dots ,a_r$ summing to $n$, count cross edges by expanding the square:ThereforeFor $n=8,r=3$, we have $q=2,s=2$, giving $(64-2\cdot 9-1\cdot 4)/2=21$. The Quadratic Turan edge bound gives $64/3$ instead: the exact correction subtracts $1/3$.

Balancing is an integer optimization with a simple reason. If two part sizes satisfy $a\ge b+2$, moving one vertex from the larger part to the smaller decreases their contribution to the sum of squares byso it increases the edge count by $a-b-1$. For eight vertices, parts $4,2,2$ give $20$ edges; moving one vertex produces $3,3,2$ and $21$ edges. The most symmetric permitted sizes pack the most cross edges, which explains the sharp construction in Turán's theorem.

How many edges can we retain while excluding a prescribed clique? For integers $r\ge 1$ and $n\ge 0$, every simple graph on $n$ vertices containing no complete subgraph $K_{r+1}$ satisfiesEquality holds exactly for the Turán graph $T_r(n)$, up to graph isomorphism. Thus the extremal number is $\mathrm{ex}(n,K_{r+1})=t_r(n)$.^[ref]

For example, $T_3(8)$ has independent sets of sizes $3,3,2$ and $21$ edges, as counted in Turán graph. It contains triangles in a graph, but no four-vertex clique. Consequently any simple graph on eight vertices with $22$ edges contains $K_4$, while $21$ edges alone do not force one. Excluding larger cliques permits denser graphs; Mantel theorem is precisely the first nontrivial case.

A short proof outline uses Zykov symmetrization. If an extremizer is not a complete multipartite graph, it has vertices $x,y,z$ with $xy,xz$ absent and $yz$ present. If either $y$ or $z$ has larger vertex degree than $x$, clone that vertex in place of $x$. Otherwise replace both $y,z$ by nonadjacent clones of $x$, gaining $2d(x)-d(y)-d(z)+1>0$ edges. Both contradict extremality; balancing the resulting at most $r$ parts gives $T_r(n)$.^[ref]

The vertex cloning in a graph step preserves clique exclusion because any clique using a clone can substitute its original vertex; nonadjacent clones cannot occur together in a clique. At most $r$ parts can be nonempty, since selecting one vertex from each gives a clique. If fewer than $r$ parts are nonempty and one has at least two vertices, splitting it creates more edges, so it cannot be extremal. For $r=1$ the bound is zero. For $r\ge n$, the Turán graph is $K_n$, and the bound is the total $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ possible edges.