Use Tutte's theorem on perfect matchings: a finite graph has a perfect matching if and only if, for every , the number of connected components of a graph of odd integer order in is at most .
First, the handshaking lemma gives , so is an even integer. Fix . For each connected component of a graph of odd integer order in , let count its edges to . Counting vertex degrees inside gives
Thus is an odd integer; it is positive because is a connected graph. If , its unique outgoing edge is a bridge. Distinct such components yield distinct bridges, so there are at most two of them. Every other such component has . Therefore
The last inequality holds because each vertex of has vertex degree three. Furthermore,
since components of even integer order do not affect parity, and is an even integer. If , this parity forces , contradicting the bound .
For , the only component is the whole connected graph, of even integer order, so . Thus every satisfies the criterion, and has a perfect matching. This proves the perfect matching theorem for a cubic graph with at most two bridges directly from Tutte's theorem on perfect matchings.
Write . Since , the one-element increment bound gives . Since ,
But gives the reverse lower bound . Hence , which is precisely . This is the matroid closure exchange property; it follows from one-element rank of a matroid increments and does not require exchanging an entire matroid basis.
List and put . Each also belongs to by (iii). Thus the definition of the closure of a matroid gives at every step. Iteration yields
In particular, collecting all elements that individually fail to increase the rank of a matroid does not create a collective increase.
Choose a maximal matroid independent set . Its cardinality is , so it is also maximal in . Apply (iv) first inside and then inside :
This proves that nested subsets of equal rank of a matroid have the same closure of a matroid.
Since is a maximal matroid independent set in , augmentation gives . For any , the rank of a matroid of equals that of . Indeed, if , either is independent and has the largest possible size , or it is dependent and is still maximal in : no element of can be added, and neither can . If , both ranks are simply .
Consequently if and only if , which proves for the closure of a matroid.
We first justify the submodularity of matroid rank, which will also support later arguments. Choose a maximal matroid independent set in , extend it to a maximal matroid independent set in , and then to one in . These extensions exist by successive additions, and their sizes are the respective values of the rank of a matroid. No element of lies in : such an element could have been added to , contradicting maximality in . Therefore is an independent subset of , giving
Now let and . If , then by (ii). Otherwise apply submodularity of matroid rank to and , whose intersection is :
The monotonicity of the rank of a matroid supplies the opposite bound , so equality holds. Thus , proving .
The rank of a matroid on a subset is
The matroid independence axioms imply that every maximal matroid independent set in has this cardinality. We write , as in the source. Directly from the definition,
For the last upper bound, deleting from any matroid independent set in leaves an independent subset of .
Up to matroid isomorphism, the numbers for are . A matroid isomorphism may relabel elements but preserves which subsets are matroid independent sets.
For , the loop of a matroid and the nonloop are different types. For , there is one type each at rank of a matroid zero and two, and two types at rank of a matroid one, distinguished by having one or two nonloops. Thus there are four.
For , the seven labelled examples of rank of a matroid one reduce to three types, distinguished by having one, two or three nonloops. The seven labelled examples of rank of a matroid two also reduce to three types: one loop of a matroid and two independent elements; no matroid loops and one pair of parallel elements of a matroid; or the uniform matroid . Different choices of labels within each description are isomorphic. Together with the unique types of rank of a matroid zero and three, this gives . The rank of a matroid, number of matroid loops and presence of parallel elements of a matroid distinguish every type just listed.
On fixed labelled ground sets of cardinality , the numbers of matroids are respectively .
For one element, the element is either a loop of a matroid or a nonloop, giving two choices. For two elements, rank of a matroid zero and two each give one possibility. At rank of a matroid one, the nonloops form any nonempty subset, giving more possibilities: total .
For three elements, classify by the total rank of a matroid. At rank of a matroid zero every element is a matroid loop; at rank of a matroid three every subset is a matroid independent set. At rank of a matroid one, choose any nonempty subset of nonloops; exactly the empty set and their singletons are matroid independent sets. This gives seven possibilities.
At rank of a matroid two, either exactly two elements are nonloops, giving three choices for the remaining loop of a matroid, or all three are nonloops. In the latter case, pairs that are matroid dependent sets define parallel elements of a matroid. There can be no such pair, giving the uniform matroid , or exactly one such pair, giving three choices. There cannot be exactly two such pairs: if and were matroid dependent sets but a matroid independent set, augmentation from to would fail. If all three pairs were matroid dependent sets, the rank of a matroid would be one. Hence rank of a matroid two gives examples.
Every listed possibility satisfies augmentation: the only nontrivial comparison on three elements is from a singleton to a two-element matroid independent set, and with at most one two-element matroid dependent set at least one addition works. The total is therefore .
With nonnegative weights, the hypergraph cut function is a symmetric set function and a submodular set function, but need not be a monotone set function. The proofs of symmetry and failure of monotonicity in (i) and (ii) still apply.
For submodularity, write , where is the indicator function that meets both sides. Fix . If , its marginal increment is zero. If , let and . Its marginal increment is
For , the middle case is absent. As grows without acquiring , can only increase, so these marginal increments can only decrease. Each therefore satisfies diminishing returns. Multiplying by and summing preserves the inequality, proving submodularity of .
No for arbitrary signed weights. Give the same single hyperedge weight . For and ,
This directly violates the defining inequality for a submodular set function.
No. Take the hypergraph with and its single hyperedge of weight . Then but , violating the monotone set function property. This example already has strictly positive weights.
Yes, for arbitrary signed weights. A hyperedge meets both and exactly when it meets both and . Therefore , and their weighted sums agree. The hypergraph cut function is a symmetric set function regardless of the signs of its weights.
For every and , including , the marginal increment is
For the empty set, this uses . The monotone set function property from (i) gives when . Consequently
Thus diminishing returns holds, so is a submodular set function by (b).
Yes: this is a monotone set function. Assume , as required by its definition at the empty set. If , every weight considered in the maximum over is considered in the maximum over , hence . If and , the minimum over is at most every weight in , hence again . No sign condition on the weights is needed.
Construct an economical two-state quantum cloner by moving both actual outputs slightly toward one another relative to the two desired copies. Set and . Their overlap is , so their sum and difference yield the orthonormal vectors
The desired outputs have the symmetric expressions
Choose the actual outputs to be
They are normalized and satisfy
Consequently the prescription , preserves the Gram matrix of the two inputs and defines a linear isometry on their span. The unitary extension of a finite-dimensional isometry gives a unitary operator on the same four-dimensional, two-qubit Hilbert space; no extra workspace is required.
For an explicit full-space construction, define , and the orthonormal basis
Choose two further orthonormal vectors perpendicular to ,
Then
maps one orthonormal basis to another and is therefore unitary. Since and , it has exactly the required two outputs.
Finally,
Both inputs therefore have the same global cloning fidelity, and so does their average:
This proves the requested existence with a two-qubit unitary gate.
Assume perfect cloning of both specified pure states. Allowing irrelevant output global phases, this would require
A unitary operator preserves inner products, and therefore their magnitudes. But the input overlap and required output overlap have different magnitudes:
This contradiction proves that no such two-qubit unitary exists, without assuming the no-cloning theorem.
For input , the controlled-NOT gate fixes , which is the ideal two-copy pure state. Thus its global cloning fidelity is . For input , the actual output is the Bell state , whereas the desired output is . Their overlap is
With the given equal input probabilities,
These values use the specified squared quantum fidelity for the full output, rather than a one-copy marginal fidelity.

Pinned article: Introduction to the OurBigBook Project

Welcome to the OurBigBook Project! Our goal is to create the perfect publishing platform for STEM subjects, and get university-level students to write the best free STEM tutorials ever.
Everyone is welcome to create an account and play with the site: ourbigbook.com/go/register. We belive that students themselves can write amazing tutorials, but teachers are welcome too. You can write about anything you want, it doesn't have to be STEM or even educational. Silly test content is very welcome and you won't be penalized in any way. Just keep it legal!
We have two killer features:
  1. topics: topics group articles by different users with the same title, e.g. here is the topic for the "Fundamental Theorem of Calculus" ourbigbook.com/go/topic/fundamental-theorem-of-calculus
    Articles of different users are sorted by upvote within each article page. This feature is a bit like:
    • a Wikipedia where each user can have their own version of each article
    • a Q&A website like Stack Overflow, where multiple people can give their views on a given topic, and the best ones are sorted by upvote. Except you don't need to wait for someone to ask first, and any topic goes, no matter how narrow or broad
    This feature makes it possible for readers to find better explanations of any topic created by other writers. And it allows writers to create an explanation in a place that readers might actually find it.
    Figure 1.
    Screenshot of the "Derivative" topic page
    . View it live at: ourbigbook.com/go/topic/derivative
  2. local editing: you can store all your personal knowledge base content locally in a plaintext markup format that can be edited locally and published either:
    This way you can be sure that even if OurBigBook.com were to go down one day (which we have no plans to do as it is quite cheap to host!), your content will still be perfectly readable as a static site.
    Figure 5. . You can also edit articles on the Web editor without installing anything locally.
    Video 3.
    Edit locally and publish demo
    . Source. This shows editing OurBigBook Markup and publishing it using the Visual Studio Code extension.
  3. https://raw.githubusercontent.com/ourbigbook/ourbigbook-media/master/feature/x/hilbert-space-arrow.png
  4. Infinitely deep tables of contents:
    Figure 6.
    Dynamic article tree with infinitely deep table of contents
    .
    Descendant pages can also show up as toplevel e.g.: ourbigbook.com/cirosantilli/chordate-subclade
All our software is open source and hosted at: github.com/ourbigbook/ourbigbook
Further documentation can be found at: docs.ourbigbook.com
Feel free to reach our to us for any help or suggestions: docs.ourbigbook.com/#contact