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.

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 crown graph is a complete bipartite graph with a perfect matching removed. For $n\ge 2$ it has chromatic number two, but greedy coloring in the order $a_1,b_1,a_2,b_2,\dots ,a_n,b_n$ uses $n$ colors: the matched pair gets the same new color, and every subsequent pair sees all earlier colors.

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.

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

For a biregular graph with $m$ left vertices of degree $r$ and $n$ right vertices of degree $s$, let $X$ be the indicator vector of a uniformly selected independent set. Use base-two information entropy. Shearer inequality gives $H(X_U)\le r^{-1}{\sum }_{w\in W}H(X_{N(w)})$. Conditional on $X_U$, each right vertex with an empty selected neighbourhood is an independent fair binary choice, and the other right vertices are forbidden. Writing $q_w=\mathbb{P}(X_{N(w)}=0)$ gives $H(X)\le r^{-1}{\sum }_w[H(X_{N(w)})+r{q}_w]$. For the $2^s$ neighbourhood patterns, assign weight $2^r$ to the zero pattern and weight one to all others. Jensen's inequality implies $H(Y)+r{q}_w\le {\log }_2(2^r+2^s-1)$. Since $n/r=m/s$, the bound follows from $H(X)={\log }_{2}i(G)$. If $s$ divides $m$, the disjoint union of $m/s$ copies of the complete bipartite graph $K_{s,r}$ attains equality: each component has $2^s+2^r-1$ independent sets.

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

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.

The octahedral graph is the graph obtained from $K_6$ by removing a perfect matching; equivalently it is $K_{2,2,2}$. Its chromatic number is three, and it contains two vertex-disjoint triangles in a graph. A complete bipartite graph with a single additional internal edge cannot contain it: every triangle in that host uses the additional edge.

Regard the two kinds of agents as the two sides of a complete bipartite graph, with edge weight $c_{ij}$. Pairing everyone is a perfect matching, and its maximum total weight is $P$. Consider the capacitated linear programIt is feasible and bounded. Every optimum has all row and column sums equal to one: otherwise the equal total deficits of the two sides give a row $i$ and column $j$ both below one. Increasing $x_{ij}$ by the smaller of their positive deficits remains feasible and increases the objective because $c_{ij}>0$, a contradiction.

Thus an optimum is a doubly stochastic matrix. By the Birkhoff-von Neumann theorem it is a convex combination of permutation matrices, so at least one corresponding perfect matching has weight at least its objective. Conversely every such perfect matching gives a feasible matrix. Hence $P_{\mathrm{LP}}=P$. One way to justify the decomposition is to apply Hall's marriage theorem to the positive-entry support, subtract the smallest entry on a supported perfect matching, and repeat after rescaling the nonzero remainder; each subtraction removes a positive entry, so the process terminates.

The dual linear program assigns nonnegative dual variables $p_i,q_j$ to the row and column capacity constraints:These are exactly the permitted payments and all the pairwise acceptance conditions, so its optimal value is $Q$. It is feasible, for example by taking $p_i={\max }_j{c}_{ij}$ and $q_j=0$. Strong duality now gives $P=P_{\mathrm{LP}}=Q$. In particular, the nonnegative payment restriction has been retained throughout; using capacity inequalities rather than equality constraints avoids introducing unrestricted prices.

For a direct weak duality check, sum $p_i+q_{\pi (i)}\ge c_{i,\pi (i)}$ over any pairing $\pi$. Its revenue never exceeds the company's total offered payment. The linear programming duality and integrality argument prove that this lower bound on payments is attained.

False. The complete bipartite graph $K_{2009,2010}$ is $2009$-connected. Deleting fewer than $2009$ vertices leaves at least one vertex in each part and therefore a connected complete bipartite graph; deleting the smaller part disconnects the larger independent set. But its two parts have unequal sizes, so a matching cannot cover them both. Equivalently it has an odd number of vertices. Thus it has no perfect matching.

No. A counterexample works for every $k\ge 2$. Take the complete bipartite graph $G=K_{k,k}$ with vertex setsIt is a k-connected graph: deleting fewer than $k$ vertices leaves at least one vertex in each side, and the remaining complete bipartite graph is a connected graph.

Chooseand order these sets so that $u_1=b_1$ and $w_1=b_2$. Order the other members arbitrarily. These are disjoint sets of cardinality $k$, and every vertex of $G$ is one of the specified endpoints.

If the prescribed $k$ vertex-disjoint paths existed, no one of them could have an internal vertex, because every vertex must serve as the endpoint of one of the graph paths. Thus each graph path would have to be a single edge. But $b_1,b_2$ lie in the same side of the bipartite graph, so there is no edge $b_1{b}_2$. This contradicts the requirement on $P_1$.

For $k=2$ this is the four-vertex cycle graph, with opposite vertices paired. The stronger property that every prescribed pairing can be realized is the linked graph property; vertex connectivity alone does not guarantee it.

At any vertex, each complete bipartite graph $K_{k,k}$ containing it contributes exactly $k$ incident edges. Since the copies partition all incident edges of the complete graph, $n-1$ is a multiple of $k$. In particular $\gcd (n,k)=1$.

If there are $b$ copies, counting their edges givesThus $k^2\mid n(n-1)$. Since $n$ is coprime to $k^2$, it can be cancelled in this divisibility, yieldingIf $n=1$, the empty partition is consistent with the same conclusion, since every positive integer divides zero.

Extremal graph theory asks how many edges a graph can have while avoiding a prescribed subgraph. Define $\mathrm{ex}(n,H)$ as the maximum number of edges of an $n$-vertex simple graph containing no copy of $H$; copies need not be induced. The extremal graph often reveals the structural reason a forbidden configuration must appear.

A complete proof of Mantel theorem illustrates this principle. In a triangle-free graph, the neighborhoods of the endpoints of any edge are disjoint, so $d(u)+d(v)\le n$. Summing over edges gives ${\sum }_{v}d(v{)}^2\le nm$, where $m$ is the edge count. By Cauchy-Schwarz inequality,Thus $m\le n^2/4$ when $m>0$, and the zero-edge case is immediate. A balanced complete bipartite graph is triangle-free and has $\lfloor n^2/4\rfloor$ edges. ThereforeThe proof links a local forbidden triangle to a global degree inequality.

The general Turan theorem states that the balanced complete $(r-1)$-partite graph $T_{r-1}(n)$ maximizes the edge count among $K_r$-free graphs. Its leading density is $(1-1/(r-1))n^2/2$. A standard symmetrization explanation is to replace a lower-degree vertex by a twin of a nonadjacent higher-degree vertex: no $K_r$ is created and the edge count does not decrease. Iterating at the level of twin classes produces a complete multipartite graph with at most $r-1$ parts. Moving vertices between parts then balances the part sizes and maximizes the number of cross edges. This provides structural intuition beyond the preceding exact triangle proof.

For any fixed graph $H$ with chromatic number $r\ge 2$, the Erdős-Stone theorem isThe lower bound is the Turan construction: an $(r-1)$-partite graph cannot contain $H$. To describe the upper-bound proof, fix an edge-density excess above $1-1/(r-1)$. Apply a regularity partition with an error parameter much smaller than that excess and a positive density threshold. Delete irregular and low-density pairs; the resulting reduced graph still has density above the Turan threshold, so it contains $K_r$. The corresponding $r$ vertex classes form pairwise regular, positive-density pairs. The embedding argument successively chooses vertices with large neighborhoods in every remaining class; regularity discards only a small exceptional set at each choice. With the parameters sufficiently small and $n$ sufficiently large, this embeds a complete $r$-partite graph with $|V(H)|$ vertices in each part, and therefore a properly colored copy of $H$. This explains why chromatic number, rather than the exact shape of $H$, controls the leading quadratic term.

For example $\chi (C_5)=3$, so forbidding a five-cycle still allows asymptotically $n^2/4$ edges, and exceeding that density by any fixed positive fraction eventually forces a five-cycle. For $K_r$ the exact Turan theorem strengthens the asymptotic statement. For bipartite $H$, the theorem gives only $o(n^2)$, leaving an important finer problem: for example $K_{s,t}$-free graphs have upper bounds of order $n^{2-1/s}$ from counting common neighborhoods. Extremal results consequently range from exact finite bounds to asymptotic density thresholds and stability questions about near-extremal structure.

In the usual nondegenerate convention, a strongly regular graph of order $n$ and parameters $(d,a,b)$ is a finite simple $d$-regular graph with $0<d<n-1$ in which adjacent vertices have $a$ common neighbours and distinct nonadjacent vertices have $b$. Its adjacency matrix of a graph $A$ obeysFor the usual nondegenerate parameters with $b>0$ the graph is connected, so eigenvalue $d$ has multiplicity one. On the perpendicular complement of the all-ones vector, $J=0$ and the possible eigenvalues areIf $r$ has multiplicity $m$, then zero trace gives $d+mr+(n-1-m)s=0$. Solving provesThe denominator is positive in this nondegenerate convention. Otherwise all eigenvalues on the all-ones complement would coincide, forcing $A=rI+(d-r)J/n$. All off-diagonal entries would then be the same, making the graph complete or edgeless. If complete graphs are admitted with arbitrary unused $b$, the printed claim needs qualification: $K_2$ with $(d,a,b)=(1,0,2)$ satisfies the common-neighbour conditions vacuously but makes the fraction $0/0$. For complete graphs with nonzero denominator, the spectral calculation still works with an unused root of multiplicity zero.

For the triangle-free graph claim, suppose first there are at least two vertices. Nonadjacent vertices have a common neighbour, so the graph is connected. If $u,v$ are adjacent, put $U=N(u)\setminus \{v\}$ and $V=N(v)\setminus \{u\}$. Every member of $U$ is nonadjacent to $v$, and exactly two of its three common neighbours with $v$ lie in $V$, the third being $u$. By symmetry every member of $V$ has exactly two neighbours in $U$. Counting these edges gives $2|U|=2|V|$, hence $d(u)=d(v)$. Connectivity makes the graph $d$-regular. Counting length-two paths from a vertex to non-neighbours givesHere $a=0$, $b=3$, and the larger-root multiplicity becomes $[n-1+d^2/\sqrt{4d-3}]/2$. Thus $t=\sqrt{4d-3}$ is rational and therefore an integer. It is odd, $d=(t^2+3)/4$, and integrality also gives $t\mid d^2$. Since $16d^2\equiv 9(\mathrm{mod}t)$, one obtains $t\mid 9$, henceThe complete bipartite graph $K_{3,3}$ realizes $d=3$: vertices in the same part have all three vertices of the other part as common neighbours, and vertices in opposite parts are adjacent. There are no triangles.

As literally worded, the one-vertex graph is a vacuous exception: it has no triangles or nonadjacent distinct pairs, but has $d=0$. The displayed positive-degree classification therefore requires at least two vertices. This qualification completes the triangle-free graphs with three common neighbours argument rather than silently excluding a counterexample.

A Steiner system $S(5,6,12)$ consists of 12 points and a collection of six-element blocks such that every five-element subset lies in exactly one block. The blocks are often called hexads. Necessarily their number is $\left(\genfrac{}{}{0ex}{}{12}{5}\right)/\left(\genfrac{}{}{0ex}{}{6}{5}\right)=132$. We give the synthematic construction of the small Witt design explicitly and prove this defining property.

Write $X=\{1,\dots ,6\}$ and $Y=\{T_1,\dots ,T_6\}$. For an unordered pair $P=\{T_i,T_j\}\subset Y$, let $S(P)$ denote the unique syntheme shared by its two synthematic totals. A duad $D\subset X$ belongs to three synthemes. The corresponding three pairs $P$ partition $Y$: every synthematic total contains $D$ in exactly one of its synthemes, and each syntheme lies in exactly two synthematic totals. Thus the incidence $D\in S(P)$ gives a perfect matching of the six synthematic totals for each duad.

To describe the blocks with three points in each half, take an unordered partition $X=A\bigsqcup A^c$ into triples. A syntheme is cross if each of its three duads joins $A$ to $A^c$. Form a graph on $Y$ by declaring $P$ an edge exactly when $S(P)$ is cross. This graph is the union of two disjoint triangles. Indeed a synthematic total partitions the nine cross duads; every syntheme has either one or three cross duads, so if $k$ of its five synthemes are cross, then $3k+(5-k)=9$, giving $k=2$. Each vertex therefore has degree two. The stronger assertion about its components follows directly for $A=\{1,2,3\}$, when the two triangles areany other triple partition is obtained by relabelling $X$, which also permutes the synthematic totals. Denote the two components by $B,B^c$.

The complete block collection is given by the following three rules:

There are $2+15\cdot 3\cdot 2+10\cdot 4=132$ distinct blocks. The first two rules have different intersection sizes with $X$ from the third; within the third, a block determines its triple $A$ and its component. We next verify the Steiner system property, rather than relying solely on this count.

We need one further consequence of the triangle construction. The three synthemes attached to the three pairs within $B$ are pairwise disjoint, since any two belong to their common synthematic total, and together they are all nine cross duads of the complete bipartite graph between $A$ and $A^c$. Thus $B$ determines the unordered partition $A\bigsqcup A^c$ uniquely: it is the bipartition of this connected graph. There are 10 such partitions, each giving two different components, hence 20 different triples in $Y$. Since $\left(\genfrac{}{}{0ex}{}{6}{3}\right)=20$, each triple in $Y$ corresponds to exactly one triple partition of $X$. The same reasoning applies to $B^c$.

Let $F$ be any five-point set and put $r=|F\cap X|$. If $r=5$, only $X$ can contain it; if $r=0$, only $Y$ can contain it, because no other block has five points in either half.

If $r=4$, set $D=X\setminus F$ and write $F\cap Y=\{T\}$. The three pairs attached to $D$ partition $Y$, so exactly one contains $T$; its block $(X\setminus D)\cup P$ is the unique block through $F$. If $r=1$, put $P=Y\setminus F$ and write $F\cap X=\{x\}$. The three duads of $S(P)$ partition $X$, so exactly one contains $x$; this gives the unique block $D\cup (Y\setminus P)$.

If $r=3$, write $A=F\cap X$ and $P=F\cap Y$. A syntheme has either one or three duads crossing $A\bigsqcup A^c$. In the one-cross case, $S(P)$ has exactly one duad $D$ internal to $A^c$, and the unique block is $(X\setminus D)\cup P$. No block with three points in each half is possible, since $P$ is then not an edge of either triangle. In the three-cross case, $P$ is an edge of exactly one triangle $B$, giving the unique block $A\cup B$; no duad of $S(P)$ is internal to $A^c$, so a block with four points in $X$ is impossible.

Finally let $r=2$, write $D=F\cap X$ and $B=F\cap Y$, and use the uniquely associated partition $X=A\bigsqcup A^c$ just proved. If $D$ crosses this partition, the three synthemes belonging to the pairs inside $B$ contain each cross duad exactly once. Thus the matching of $Y$ attached to $D$ has exactly one pair internal to $B$. It has exactly one pair $P$ internal to $B^c$ as well, since a matching must leave equal numbers of vertices in the two halves for cross pairs. The unique block containing $F$ is then $D\cup (Y\setminus P)$; $D$ is not contained in either $A$ or $A^c$, so no block of the third rule applies. If $D$ is internal to $A$ or $A^c$, none of its attached pairs lies inside $B$ or $B^c$, since the synthemes attached to these internal pairs are cross. Thus the second rule gives no block. The third rule gives exactly one, namely $A\cup B$ or $A^c\cup B$, according to which part contains $D$.

All possibilities have now been exhausted, provingThis is the small Witt design; the construction uses only duads, synthemes, their synthematic totals, and the induced action on those synthematic totals.

False. The complete bipartite graph $K_{3,3}$ has chromatic number two, but is nonplanar. For example a simple bipartite plane graph has $e\le 2v-4$, because all facial cycles have length at least four; $K_{3,3}$ has $v=6$, $e=9>8$.