We construct an injection from the unmatched vertices in a matching to the leaves of a rooted tree. Start a downward graph path at each unmatched vertex $u$. If the current vertex is a leaf of a rooted tree, stop. Otherwise choose any child $v$. The current vertex is either the unmatched starting point or a vertex already matched to its own parent.

In either case, $v$ cannot be unmatched: the proper matching in a rooted tree condition would require its parent to be matched to one of $v$'s siblings in a rooted tree, whereas that parent is either unmatched or already matched upward. Nor can $v$ be matched to its parent. Its matching partner must therefore be one of its own children, say $w$. Extend the graph path by the two edges to $v$ and then to $w$, and continue from $w$.

Every extension descends two levels, so finiteness guarantees termination at a leaf of a rooted tree. Every visited vertex except the starting point is matched. The constructed graph paths for different unmatched starting points are disjoint: if two downward graph paths in a tree meet, one starting point must lie on the other path, which would put a second unmatched vertex after the first. That is impossible. Hence their terminal leaves of a rooted tree are distinct, provingOnly the properness condition for unmatched non-root vertices was used. If the root is unmatched and the convention exempts it because it has no parent, the same construction starts there and still works. Thus the root convention does not affect the claimed inequality. This proves the unmatched-vertex bound for a proper tree matching without requiring $M$ to have maximum size.

In depth-first search of an undirected graph, every edge joins a vertex to one of its ancestors or descendants in the discovery tree. To see this directly, suppose $u$ is discovered before its neighbour $v$. If $v$ is still undiscovered, the search from $u$ cannot finish before discovering $v$: it eventually scans $uv$. Thus $v$ is discovered while the call for $u$ remains active and belongs to its descendant subtree.^[ref]

For any edge $uv$, its ancestor endpoint therefore has a proper descendant and hence at least one child. It is an internal vertex of a rooted tree. Every edge has an internal endpoint, so the internal vertices form a vertex cover. The relevant leaves of a rooted tree here have no children in the rooted discovery tree; a root of vertex degree one can still be internal.

Root the tree arbitrarily. For each vertex $v$, let $D_1(v)$ be the minimum vertex cover size in its descendant subtree, conditional on selecting $v$, and $D_0(v)$ the corresponding minimum conditional on omitting $v$. Process the vertices in postorder traversal. For every child $u$ of $v$,At a leaf of a rooted tree, the empty sums give $D_1=1,D_0=0$. Return $\min \{D_0(r),D_1(r)\}$ at the root $r$.

For algorithm correctness, if $v$ is selected, each child subtree may independently use its cheaper state, since the connecting edge is already covered by $v$. If $v$ is omitted, each child must be selected to cover its connecting edge. Distinct child subtrees have no edges between them because the input is a tree. These observations prove the recurrences by structural induction. Each edge contributes constant work once, giving $O(|V|)$ time complexity and $O(|V|)$ space with adjacency lists. The single-vertex tree correctly has optimum zero. This is minimum vertex cover of a tree by dynamic programming.

Construct a set cover problem instance whose universe is the set of edges $E$. For each vertex $v\in V$, supply the set $S_v$ of all edges incident to $v$. A collection $\{S_v:v\in C\}$ covers the universe if and only if every edge has an endpoint in $C$, which is precisely the vertex cover condition.

The correspondence preserves cardinality: a vertex cover of size $k$ is a feasible solution of the set cover problem using $k$ of these sets, and conversely. If two labelled vertices produce identical sets, one can keep their labels or discard duplicate choices without changing the optimum. The construction has size $O(|V|+|E|)$ when incidences are listed, so it is a polynomial-time reduction.

For a finite undirected graph $G=(V,E)$, a vertex cover is a subset $C\subseteq V$ meeting every edge: for every $\{u,v\}\in E$, at least one of $u,v$ belongs to $C$. The optimization problem asks for a vertex cover of minimum cardinality. Its usual decision version also supplies an integer $k$ and asks whether one exists with $|C|\le k$.

Use the usual bottom-up splaying operations. We prove the stronger result that at most three successful calls suffice. No insertions or deletions are needed.

If the chosen key $x$ is the minimum stored key, first perform splaying on $x$ and then on its immediate successor. The argument for consecutive keys in a binary search tree makes $x$ the left child of the successor with an empty right subtree; minimality makes its left subtree empty too. Hence $x$ is a leaf of a rooted tree. The maximum-key case is the mirror image.

Suppose $x$ is an interior key. Since at least four keys are stored, there are either two keys larger than $x$ or two smaller than $x$. In the former case choose four consecutive stored keyswhere $a$ is the predecessor of $x$, and $b,c$ are the next two successors. Perform $\mathrm{Splay}(c),\mathrm{Splay}(a),\mathrm{Splay}(b)$.

Here is a complete check of the local shapes. After the first call, $c$ is the root. After the second, $a$ is the root; every key below $a$ is in its left subtree $A$, and every key above $c$ stays in the right subtree $D$ of $c$. These outside subtrees cannot interfere with the next search. Between $a$ and $c$ there are only $x,b$. The last step of splaying on $a$ is either a zig step, leaving $c$ as its right child; a zig-zag step, with the same result; or a zig-zig step, leaving some $p\in \{x,b\}$ as its right child with $c$ immediately to the right of $p$. Consequently the possible right subtrees of $a$ are exactly among these four forms, using $k(L,R)$ for a node with its left and right subtrees:Here an unexpanded $x$ or $b$ denotes a node with no children. Each row follows by the indicated one or two tree rotations in each bottom-up step. All rows end with $x$ as the right child of $a$, with both its subtrees empty. If instead two keys below $x$ are available, reflect the construction, exchanging left and right and reversing the order of keys. This proves splaying a chosen node into a leaf for every node of every splay tree of size at least four.

Write $y=x+1$. After splaying on $x$, that key is at the root, and $y$ is the smallest key in its right subtree. This uses the integer assumption: no stored key lies strictly between $x$ and $y$. Thus $y$ has an empty left subtree while it remains within the right subtree of $x$.

Now perform ordinary bottom-up splaying on $y$. Until the final step involving $x$, all tree rotations occur below $x$ and leave it at the root. There are only two possible final cases.

Therefore $x$ becomes the left child of $x+1$. The argument applies more generally to consecutive keys in a binary search tree, even when their numerical difference is not one.

Use the conventional bottom-up red-black tree insertion: insert a red node by the binary search tree rule, repair a red parent with recolouring or tree rotations, and make the root black. Write $B$ and $R$ for black and red. The first three insertions give root $34_B$, with $21_R$ on the left and $55_R$ on the right.

Inserting $40$ as the left child of $55$ gives a red parent and a red uncle. Recolour $21,55$ black and retain a black root $34$. Inserting $45$ then gives the inner configuration $55_B$–$40_R$–$45_R$. A left tree rotation at $40$, followed by a right tree rotation at $55$, produces a subtree rooted at $45_B$ with $40_R$ and $55_R$ beneath it. Finally insert $37_R$ to the left of $40_R$. Its uncle $55_R$ is red, so recolour $40,55$ black and $45$ red. No further repair is required because $45$ has black parent $34$.

The final root is $34_B$; its left child is $21_B$ and its right child is $45_R$. Under $45_R$ are $40_B$ on the left and $55_B$ on the right; $40_B$ has left child $37_R$. All omitted children are black null sentinels. Each root-to-null graph path has two real black nodes, and no red node has a red child.

No. In a red-black tree with no red nodes, equal black height forces every graph path from the root to an absent-child position to have the same length. A real node cannot have exactly one real child: the two paths through that node would then have different numbers of black nodes. Recursively, every real level must be full. The tree is therefore a perfect binary tree.

With $h$ real levels its size is $1+2+\cdots +2^{h-1}=2^h-1$. A size of $23$ would require $2^h=24$, which is impossible for an integer $h$. The black null sentinels are not counted among the $23$ stored entries. This is the all-black red-black tree size criterion.

First perform splaying on the key to be deleted, making its node the root of a tree. Delete that root, leaving left and right subtrees $L,R$. If either is empty, return the other. Otherwise find the maximum key $m$ of $L$ by following right-child references, and perform splaying on $m$ within $L$. This makes $m$ the root of $L$ with an empty right subtree. Attach $R$ there. The result is the original splay tree with exactly the selected key removed. An unsuccessful lookup leaves the represented set unchanged.

For algorithm correctness, all keys of $L$ are smaller than the deleted key, and all keys of $R$ are larger. Splaying preserves the binary search tree property by the permitted assumption. Since $m$ is the maximum of $L$, it has no larger key within $L$; since every key of $R$ exceeds $m$, attaching $R$ as its right subtree preserves every ordering condition. All remaining keys occur once. This is the join-based deletion of a splay tree.^[ref]

A binary search tree is a binary tree storing distinct keys from a total order, with every key in a node's left subtree smaller than that node's key and every key in its right subtree larger. The condition concerns entire subtrees, not just immediate neighbours.

For membership, start at the root of a tree and compare the target with the current key. Return true on equality; continue into the left subtree for a smaller target and the right subtree for a larger target; return false on an empty subtree. The binary search tree ordering ensures that a discarded subtree cannot contain the target. Each step descends one level, so the algorithm terminates and uses $O(h+1)$ time complexity for height of a binary tree $h$, under constant-time key comparison.

Order the edges arbitrarily and fix their colours one at a time. After a partial assignment $P$, regard all unassigned edges as independent fair red/blue choices, and computeThe conditional expectation of a monochromatic clique count is easy to compute. For each four-vertex subset $A$, let $r$ be the number of its six edges still unassigned. Its contribution $q_A(P)$ to $Q(P)$ isIn the second case, every remaining edge must match the already fixed colour; this includes a completely fixed monochromatic copy, for which $r=0$ and the contribution is one. In the last case, the six unassigned edges may become either all red or all blue. By linearity of expectation,For the next unassigned edge $e$, compute $Q(P,e=\text{red})$ and $Q(P,e=\text{blue})$. The law of total expectation givesChoose the colour with the smaller value, resolving a tie by a fixed rule. At least one is at most their average, so the loop invariant is that $Q$ never increases. Initially $Q=\left(\genfrac{}{}{0ex}{}{n}{4}\right)/32$; once every edge is fixed, there is no randomness left and $Q=Z$. Therefore the method of conditional expectations guaranteesA direct implementation recomputes both sums over all $O(n^4)$ four-vertex subsets for each of the $O(n^2)$ edges, requiring $O(n^6)$ arithmetic operations. The comparisons can be exact: every contribution is a multiple of $1/32$, so store $32Q$ as an integer with $O(\log n)$ bits. This gives $O(n^6\log n)$ bit complexity with elementary arithmetic, and hence a deterministic polynomial time construction. No random sampling is performed by this derandomization.

Set $N=\left(\genfrac{}{}{0ex}{}{n}{4}\right)$. Independently sample an edge coloring exactly as in part (d), count its monochromatic copies of $K_4$ by examining all four-vertex subsets, and accept precisely when $32Z\le N$. Otherwise start over with a fresh edge coloring.

To prove an expected polynomial time bound, the existence argument alone is insufficient: we need a lower bound on the acceptance probability at this exact threshold. Since $32Z$ is a nonnegative integer with expectation $N$, rejection implies $32Z\ge N+1$. Markov's inequality therefore gives the integer-valued expectation threshold restart boundThe number of attempts has a geometric distribution, with expectation at most $N+1$. Sampling the edge coloring costs $O(n^2)$ random bits, and checking all $N$ four-vertex subsets costs $O(n^4)$ operations, since only six edges must be tested per subset. HenceThis is a randomized algorithm that always returns an edge coloring meeting the original threshold and terminates with probability one. The stated operation count uses $O(\log n)$-bit counters; counting their bit complexity explicitly introduces at most a further logarithm factor and still gives polynomial time. For $n<4$, return any edge coloring immediately.

Colour each edge of the complete graph $K_n$ independently red or blue, with probability $1/2$ for each colour. Every four-element subset $A$ of vertices determines exactly one copy of $K_4$, containing six edges. These six edges are all red with probability $2^{-6}$ and all blue with probability $2^{-6}$. The events are disjoint events, soLet $I_A$ be the indicator random variable for this event and let $Z={\sum }_A{I}_A$ count the monochromatic copies. Linearity of expectation givesThe indicator random variables for overlapping copies need not be independent. Averaging over all edge colorings ensures that at least one has $Z\le \mathbb{E}Z$. Thus the probabilistic method provesFor $0\le n<4$, both sides are zero and any edge coloring works. Copies are counted by their four-vertex subsets, rather than by their $4!$ possible labellings.

Use uniform balanced binary sequence sampling by choosing the positions of the heads. Number the $2n=2^m$ positions from zero to $2n-1$. Start with no selected positions. Repeatedly toss the fair coin $m$ times, interpret the resulting bits as a position, and select that position if it has not already been selected; otherwise discard this block of tosses and retry. Stop when $n$ distinct positions have been selected. Put heads at those positions and tails everywhere else.

After $s$ positions have been selected, every one of the remaining positions has the same probability of being the next new position. This follows either by summing a geometric series over rejected blocks or by conditioning a uniform distribution on a finite set on avoiding the selected positions. Every ordered list of $n$ distinct selected positions consequently has probabilityEach fixed $n$-element subset has $n!$ such orders, so its probability isThus every balanced binary sequence is equally likely.

When $s$ positions are selected, a block succeeds with probability $(2n-s)/(2n)$, so the geometric distribution gives expectation $2n/(2n-s)$ blocks until the next new position. By linearity of expectation, the total expected toss count isThe strict inequality holds since $s<n$, making each term less than two. A Boolean array records membership of each position; initializing it and constructing the output require $O(n)$ additional work. The scheme terminates with probability one, since every stage has positive success probability.

Betty's scheme is biased for every $n\ge 2$. The output $H^n{T}^n$ occurs precisely when the first $n$ tosses are heads: the algorithm stops there and appends $n$ tails. ThusFor comparison, take the output $(HT{)}^n$. Its first $2n-2$ symbols contain $n-1$ heads and $n-1$ tails, so neither stopping threshold has been reached. The next symbol is the $n$th head, at which point the last tail is appended. Its unique generating prefix has length $2n-1$, givingThereforeThe faster stopping rule does not produce a uniform distribution on a finite set of balanced binary sequences. For example, at $n=2$ the six outputs have the following exact probabilities:

For $n=1$, the two possible outputs each have probability $1/2$, so that special case is uniform. For $n=0$, simply return the empty output.

A trial of Amy's rejection sampling uses exactly $2n$ fair Bernoulli trials. Exactly $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$ of the $2^{2n}$ equally likely binary sequences have $n$ heads, so the acceptance probability isIndependent retries make the number $T$ of trials a geometric random variable on $\{1,2,\dots \}$ with expectation $1/p_n$. The total number $C$ of coin tosses is $2nT$, soUsing Stirling's approximation, the central binomial coefficient satisfiesConsequentlyThe rejection sampling output is uniform among the balanced binary sequences: they have equal probability on every trial, and conditioning on acceptance preserves that equality. For $n=0$, the empty output needs zero tosses; the formula above concerns $n\ge 1$.

The expectation from part (f) is the average of $|S(\sigma )|$ over the finite collection of permutations. At least one value is as large as its average. By part (e), the corresponding $S(\sigma )$ is an independent set, soHere $\alpha (G)$ is the independence number. Since its value is an integer, one can equivalently round the right side up with the ceiling function. This application of the probabilistic method is the Caro-Wei bound.

Choose a uniform random permutation of the $n$ vertices, giving every one of the $n!$ orders the same probability. For a fixed vertex $i$, consider $i$ together with its $d_i$ graph neighbours. The relative order of these $d_i+1$ vertices is uniform, so each is equally likely to be first. The membership rule for $S(\sigma )$ therefore givesLet $I_i$ be the indicator random variable of this event. The cardinality is $|S(\sigma )|={\sum }_{i=1}^n{I}_i$, and linearity of expectation givesThe indicator random variables are generally dependent; only the uniform random permutation and linearity of expectation were needed. An isolated vertex has $d_i=0$ and is always included, as the formula correctly predicts.

Consider any edge $\{u,v\}$ of the simple graph. One endpoint comes first in the permutation $\sigma$; suppose it is $u$. Then $v$ has a graph neighbour preceding it, namely $u$, so $v\notin S(\sigma )$. Therefore no edge has both endpoints in $S(\sigma )$:This argument uses only the order of the endpoints, with no random choice required.