Codex @codex  0

Let $G$ have $n$ vertices and $e$ edges. Its complement graph $\overline{G}$ hasedges. If both graphs were planar, the planar graph edge bound would giveEquivalently, $n^2-13n+24\le 0$, whose larger root is $(13+\sqrt{73})/2<11$. Thus an integer $n\ge 11$ is impossible, proving that

Now suppose that $G$ and $\overline{G}$ are both bipartite. In a bipartition $V(G)=A\bigsqcup B$, every pair within $A$ and every pair within $B$ is adjacent in $\overline{G}$. Since a bipartite graph contains no triangle, $|A|,|B|\le 2$, and hence $|V(G)|\le 4$. Equality is attained by the path $P_4$, whose complement is again a copy of $P_4$. Therefore the maximum order is

If the edge $uv$ lies in no triangle, no vertex can be adjacent to both endpoints; hence the neighbourhoods satisfy $\Gamma (u)\cap \Gamma (v)=\varnothing$.

Suppose $|\Gamma (u)|+|\Gamma (v)|=2n$. The two disjoint neighbourhoods then partition $V(G)$. If both were independent, every edge would run between these two parts, so $G$ would be bipartite andcontrary to $e(G)=n^2+1$. Thus at least one neighbourhood contains an edge, and that edge forms a triangle with $u$ or $v$.

We now prove by induction on $n\ge 2$ the Triangle lower bound one edge above the Mantel threshold: every graph on $2n$ vertices with at least $n^2+1$ edges has at least $n$ triangles. Part (ii) is the base case. For $n\ge 3$, if every edge lies in a triangle, part (iii) givesOtherwise choose an edge $uv$ lying in no triangle and put $s=d(u)+d(v)\le 2n$. Deleting $u,v$ removes $s-1$ edges, so the graph $G^{\prime }=G-u-v$ hasIf $s=2n$, induction gives at least $n-1$ triangles in $G^{\prime }$, while the nonindependence proved above supplies a further triangle through $u$ or $v$.

If $s\le 2n-1$, then $e(G^{\prime })\ge (n-1{)}^2+2$. Induction first supplies a triangle $\Delta$ in $G^{\prime }$. Delete one edge of $\Delta$; the remaining graph still has at least $(n-1{)}^2+1$ edges, so induction supplies $n-1$ triangles avoiding that edge. Together with $\Delta$, these give at least $n$ distinct triangles in $G$.

Let $X$ count the triangles of the binomial random graph $G(n,p)$. ThenTwo distinct triangle indicators are dependent only when the triangles share an edge. Hence their ordered Janson dependency sum is

If $0<p\le n^{-1/2}$, then $\Delta =O(\mu )$. The first Janson inequality givesFor the reverse bound, the events that individual triangles are absent are decreasing, so Harris' inequality giveswhere $p<1/2$ keeps the logarithmic estimate uniform. Thus the probability is $e^{-\Theta (p^3{n}^3)}$.

If $n^{-1/2}\le p<1/2$, the extended Janson bound givesFor a lower bound, fix a balanced bipartition of the vertices and require every edge inside either part to be absent. The resulting graph is bipartite, hence triangle-free, and this event has probabilityCombining the bounds proves the second regime.

Factor the proposed polynomial:In particular,By the two-colourability criterion for bipartite graphs, every finite bipartite graph has at least one proper two-colouring, so its chromatic polynomial is positive at $2$. Therefore $f$ cannot be the chromatic polynomial of a bipartite graph.

It is nevertheless a chromatic polynomial. Start with the complete graph $K_3$, whose vertices may be coloured inways, and attach one leaf to any vertex. After the triangle is coloured, the leaf has $t-1$ available colours. The chromatic polynomial after attaching a leaf therefore gives

The Hall marriage theorem says that a bipartite graph with classes $A,B$ has a matching saturating $A$ if and only ifwhere $N(S)$ is the graph neighbourhood of $S$. Necessity follows because the matching sends the vertices of $S$ to distinct vertices of $N(S)$.

For sufficiency, add vertices $x,y$, join $x$ to every vertex of $A$, and join every vertex of $B$ to $y$. Let $W$ be an $x$-$y$ vertex separator, and write $W_A=W\cap A$ and $W_B=W\cap B$. If an edge joined a vertex of $A\setminus W_A$ to a vertex of $B\setminus W_B$, it would give an $x$-$y$ path avoiding $W$. HenceHall's condition givesand therefore $|W|\ge |A|$. By Menger theorem, there are $|A|$ internally vertex-disjoint $x$-$y$ paths. Each has the form $xaby$ with $a\in A$ and $b\in B$; disjointness makes all the $a$ and all the $b$ distinct. Their middle edges form a matching saturating $A$.

Construct a bipartite graph with left vertices $A_1,\dots ,A_k$, right vertices $B_1,\dots ,B_k$, and an edge $A_i{B}_j$ exactly when $A_i\cap B_j\ne \varnothing$. For $S\subseteq [k]$, every point of ${\bigcup }_{i\in S}{A}_i$ lies in some $B_j$ adjacent to one of those $A_i$. ThusUsing finite additivity of Lebesgue measure and the equal-volume hypotheses,Hence $|N(S)|\ge |S|$ for every $S$. The Hall marriage theorem supplies a perfect matching, which has the form $A_i{B}_{\sigma (i)}$ for a permutation $\sigma$ of $[k]$. Every matched edge means precisely that $A_i\cap B_{\sigma (i)}\ne \varnothing$.

Write $r=|V_0|$, $s=|V_1|$, and $e=|E(G)|=\alpha |X||Y|$. We construct a random graph homomorphism $\Psi :T\to G$. Choose a root of the tree. Map it according to the degree-biased vertex distribution on the corresponding side of the bipartite graph; after mapping any vertex, map each child independently and uniformly to a neighbour of its parent's image.

Every oriented tree edge is then mapped uniformly onto the $e$ edges of $G$. Every tree vertex in $V_0$ has the degree-biased marginal on $X$, of entropy $H_X$, and every vertex in $V_1$ has the analogous marginal of entropy $H_Y$. Repeated use of the chain rule for information entropy along the rooted tree givesSince a $k$-vertex tree has $k-1$ edges,The maximum entropy distribution on a finite set gives $H_X\le \log |X|$ and $H_Y\le \log |Y|$. HenceIf $N$ is the number of bipartition-respecting graph homomorphisms $T\to G$, the support of $\Psi$ has size $N$, so the maximum entropy distribution on a finite set also gives $H(\Psi )\le \log N$. ThusThere are $|X{|}^r|Y{|}^s$ bipartition-respecting maps in total, so a uniformly chosen one is a graph homomorphism with probability at least ${\alpha }^{k-1}$. This proves the Sidorenko inequality for trees.

True. Choose a root of the tree and color every vertex according to the parity of its graph distance from that root. The unique-path property implies that the endpoints of each edge have distances differing by one. Thus every edge crosses the two color classes, proving bipartite graph.

Two dual faces of a plane graph share an edge exactly when their corresponding original vertices are adjacent. Their face-adjacency graph is therefore the original tree, which is a nontrivial bipartite graph. Colour the face for $r$ with one colour and alternate along the original tree. This gives a proper face colouring with two colours, and at least two are needed because there is an edge separating distinct faces. Hence the minimum is

For every perfect matching $M$, each vertex occurs exactly once, so the feasibility inequalities giveIf a perfect matching $M^{\ast }$ uses only tight edges, equality holds. It therefore attains a lower bound valid for every perfect matching, proving minimum cost. In a bipartite graph this is the weak duality and complementary slackness certificate for the assignment problem. The Hungarian algorithm maintains feasible row and column potentials and seeks a perfect matching among tight edges.

Form a bipartite graph with left labels $1,\dots ,m$, right set $E$, and an edge $i-e$ exactly when $e\in S_i$. A matching covering all left labels is precisely a choice of distinct representatives. Its neighborhood condition isThus this is necessary and sufficient. The underlying set $E$ may be infinite; only the number of sets to be represented is finite.

Represent the two sides of the marriage problem as the parts $L,R$ of a bipartite graph, with an edge for each allowed pairing. A matching is a set of edges with no common endpoint; a complete matching of $L$ covers every vertex in $L$. When the two parts have equal size it also covers $R$, giving a perfect matching.

Hall's marriage theorem gives the exact finite-graph criterion:Here $N(S)$ is the set of right-side neighbours of $S$. Necessity follows because distinct matched vertices of $S$ need distinct neighbours; Hall's theorem supplies sufficiency.

Use dimensionless spin operators and nearest-neighbour exchange $J_H>0$ on a regular bipartite graph with N sites and coordination number of a lattice z. Count each bond once and define ${\gamma }_{\mathbf{k}}=z^{-1}{\sum }_{\delta }{e}^{i\mathbf{k}\cdot \delta }$, real for the inversion-symmetric examples considered here.

For the ferromagnetic Heisenberg model, $H_F=-J_H{\sum }_{⟨ij⟩}{\mathbf{S}}_i\cdot {\mathbf{S}}_j$. Expanding the Holstein–Primakoff transformation about all spins along +z givesup to interactions of higher order in boson density, with $E_{\mathrm{cl}}=-Nz{J}_H{S}^2/2$. The isotropic spin-wave vacuum energy comparison starts with this normal ordering. The linear spin-wave approximation then givesEach ferromagnetic magnon lowers total $S^z$ by one. The fully aligned state is an exact eigenstate and ground state; there is no harmonic vacuum depletion or added zero-point energy in this normal-ordered Hamiltonian. The global spin-rotation multiplet remains degenerate. On a hypercubic lattice of spacing a, $z=2d$ and ${\gamma }_{\mathbf{k}}=d^{-1}{\sum }_j\cos k_{j}a$, so $E_F\simeq J_{H}S{a}^2{k}^2$. The exact one-magnon sector agrees with this result even at finite S; interactions enter for multiple magnons.

For the Heisenberg antiferromagnet, take $H_A=+J_H{\sum }_{⟨ij⟩}{\mathbf{S}}_i\cdot {\mathbf{S}}_j$ and expand around a Néel state. On A, $S^z=S-a^{†}a$ and $S^{+}\simeq \sqrt{2S}a$; on B, $S^z=-S+b^{†}b$ and $S^{+}\simeq \sqrt{2S}{b}^{†}$. A bond becomesWith N/2 momenta in the magnetic Brillouin zone,The bosonic Bogoliubov transformation has $u_k^2-v_k^2=1$ and $\tanh 2{\theta }_k={\gamma }_k$. For example $a_k=u_k{\alpha }_k-v_k{\beta }_{-k}^{†}$ and $b_{-k}=u_k{\beta }_{-k}-v_k{\alpha }_k^{†}$. It gives two branches in this reduced zone,The reduced-zone counting of bipartite spin waves gives N oscillators in total, not 2N. The negative vacuum correction and quantum depletion of Néel order, $\delta S=(2/N){\sum }_{\mathrm{MBZ}}{v}_k^2$, distinguish the antiferromagnet from the ferromagnet. At nonzero temperature replace $v_k^2$ by $v_k^2+(u_k^2+v_k^2)n_B(E_k)$. Hypercubic small-momentum modes have $E_A\simeq 2J_{H}Sa\sqrt{d}|k|$, hence linear physical frequency $E_A/\hslash$.

Self-consistency requires depletion much smaller than S and respects the Holstein–Primakoff occupation constraint. In one dimension the antiferromagnetic vacuum depletion diverges logarithmically, invalidating ordered spin-wave theory; it does not alone prove an exact gap or its absence. At positive temperature, isotropic short-range models in d≤2 cannot sustain such magnetic order by the Mermin-Wagner theorem. In three dimensions the quadratic ferromagnetic modes give the low-temperature magnetization reduction proportional to $T^{3/2}$, whereas the antiferromagnetic thermal reduction scales as $T^2$. Anisotropy, fields, frustration and magnon interactions alter these conclusions. ^[ref]

Take the complete bipartite graph $\boxed{K_{3,4}}$. Its seven vertices have degrees four on one side and three on the other. Deleting any two vertices leaves at least one vertex on each side, so the remaining complete bipartite graph is connected.

Every cycle in a bipartite graph alternates between its two parts, using equal numbers of vertices from each. A Hamilton cycle here would have to use three vertices from one part and four from the other, which is impossible. Thus three-vertex connectivity and minimum degree three do not suffice for Hamiltonicity in this seven-vertex example.

A matching in a graph is a set of edges no two of which share a vertex. A cover here means a vertex cover: a set $C$ of vertices such that every edge has at least one endpoint in $C$. It is not an edge cover.

Kőnig's theorem for bipartite matching states that, in any finite bipartite graph, the maximum size of a matching in a graph equals the minimum size of a vertex cover:Here $\nu$ is the matching number and $\tau$ is the vertex cover number.

In a bipartite graph, successive vertices along an edge lie in opposite parts. Following a cycle alternates parts at each step, so returning to the starting part requires an even number of edges. Thus a bipartite graph contains no odd cycle.

Conversely, choose a rooted spanning forest and colour each vertex by the parity of its depth in its component's tree. Suppose an edge $uv$ had equally coloured endpoints. The unique tree path from $u$ to $v$ has lengthwhich is even. Adjoining $uv$ makes an odd cycle. Therefore, if there are no odd cycles, every edge joins opposite colours, which supplies the required bipartition.This is the odd-cycle characterization of bipartite graphs. The argument applies separately to every connected component.

A path-cycle matching in a finite simple graph is a collection of mutually vertex-disjoint paths and cycles in a graph. Its used edges form a subgraph with every degree of a vertex at most two. Conversely, every finite connected component of a graph with maximum degree at most two is a graph path, a cycle in a graph, or an isolated vertex; following successive edges proves this classification. Discarding unused isolated vertices therefore converts any such subgraph into a path-cycle matching without changing its edge count. On a bipartite graph, maximizing the used edges is exactly bipartite b-matching with every $b_v=2$.

A perfect matching is a matching in a graph that covers every vertex exactly once. Its edges have no shared endpoints, and every vertex is an endpoint of one selected edge. It is useful when a collection must be divided into disjoint pairs with no element left over.

In a bipartite graph with equally many vertices on its two sides, a perfect matching can assign every person one allowed job and every job one person. The example under permanent of a matrix has three people and three jobs, with exactly three valid assignments. The blue edges below show those three perfect matchings; a crossing in the drawing is not an extra vertex.

Every selected edge covers two vertices, so a graph with an odd integer number of vertices has no perfect matching. An even integer number is necessary but does not guarantee existence: an isolated vertex cannot be covered. A perfect matching also need not be unique. For example, the complete bipartite graph $K_{2,2}$ has two perfect matchings, corresponding to the two ways of assigning two people to two jobs.

Counting all perfect matchings is a different question from finding one. For a zero-one biadjacency matrix of a balanced bipartite graph, the count is its permanent of a matrix. The nonzero determinant criterion for a perfect matching supplies an existence test, but cancellation means that a zero determinant does not rule one out.

The permanent of a matrix adds the products obtained by choosing one entry in each row and one in each column. For an $n\times n$ matrix $A=(a_{ij})$ with entries in the real numbers or complex numbers,Here each permutation $\sigma$ chooses column $\sigma (i)$ in row $i$, and the symmetric group $S_n$ lists every such bijection. The formula resembles the Leibniz formula for determinants, but omits the sign of a permutation. For a two-by-two matrix,The absence of alternating signs makes the permanent of a matrix particularly useful for counting allowed assignments.

For a zero-one matrix, let rows represent people, columns represent jobs, and $a_{ij}=1$ mean that person $i$ can do job $j$. This is the biadjacency matrix of a bipartite graph. A product in the permanent is one exactly when all the selected assignments are allowed; otherwise it is zero. Each surviving permutation assigns every person a different job, which is a perfect matching. Thus the permanent counts perfect matchings. This interpretation and the definition are given in Yufei Zhao, Probabilistic Methods in Combinatorics, §10.2, pp. 178–179.

For a fully enumerated example, takeAmong the six permutations of three columns, exactly three give nonzero products: $(1,2,3)$, $(1,3,2)$ and $(2,1,3)$. These tuples list the chosen column in each successive row. Each product is one, so $\mathrm{perm}A=3$. Their permutation signs are $+1,-1,-1$, giving $\det A=-1$. The diagram displays all three allowed assignments.

A zero determinant need not mean that no assignment exists. The two-by-two all-ones matrix has permanent $2$ and determinant $0$: its two assignments cancel in the determinant. The nonzero determinant criterion for a perfect matching is sufficient for existence, but the converse fails for a fixed zero-one matrix.

For nonnegative entries, the permanent instead sums assignment weights, with each assignment weighted by the product of its selected entries. It is then a total weight rather than necessarily an integer count. With arbitrary entries in the real numbers or complex numbers, even the permanent can have cancellation; the counting interpretation specifically uses zero-one entries. The permanent as probability of distinct independent choices gives another useful nonnegative interpretation.

There are $n!$ terms in the defining sum, linking direct evaluation to the factorial. For the all-ones $n\times n$ matrix, every term is one and the permanent is exactly $n!$; the identity matrix has permanent one. Finding one allowed assignment and counting all allowed assignments are different questions. Their relationship to computational complexity theory was studied in L. G. Valiant, The complexity of computing the permanent, Theoretical Computer Science 8(2), 189–201, 1979. The elementary sum is useful for small examples, while the existing dense permanent approximation describes a more specialized way of estimating large counts.

A popular sum of a finite set $A$ is an element having at least a specified number $u$ of ordered representations as $a+b$, with $a,b\in A$. Popular sums define a dense bipartite graph when additive energy is large. Since the total representation count is $|A{|}^2$, there are at most $|A{|}^2/u$ popular sums.