Consider the following original five-<vertex> <simple graph>, where $AB$ denotes the undirected <edge> $\{A,B\}$:
$$
V=\{A,B,C,D,E\},\qquad E=\{AB,BC,CD,DE,EA,AC,BD\}.
$$
Its seven <edges> give initial <expected value> $q(\varnothing)=7/2=3.5$. Use <vertex> order $A,B,C,D,E$ and choose zero whenever the two child <conditional expectations> tie.

\Image[/conditional-expectations-graph-cut.png]
{title=A guaranteed five-edge cut and a six-edge maximum cut of the same graph}
{description=The <conditional expectations cut example> uses the same original <simple graph> in both panels. Node colours and labels identify the two sides of each <cut of a graph>. Solid teal <edges> cross; dashed grey <edges> do not. The deterministic choices on the left give five crossing <edges>; the assignment on the right gives six. Crossings of drawn lines are not additional <vertices>.}

The complete decision ledger is below. A prefix lists fixed labels in <vertex> order; all later labels remain hypothetically <independent> fair <bits>. Each candidate entry is the <conditional expectation> of the final <cut of a graph>, including the contribution of unresolved <edges>.

|| Prefix before choice
|| Next <vertex>
|| Set to 0
|| Set to 1
|| Chosen label
|| Retained <conditional expectation>

| Empty
| $A$
| $3.5$
| $3.5$
| $0$
| $3.5$

| $0$
| $B$
| $3$
| $4$
| $1$
| $4$

| $01$
| $C$
| $4$
| $4$
| $0$
| $4$

| $010$
| $D$
| $4$
| $4$
| $0$
| $4$

| $0100$
| $E$
| $3$
| $5$
| $1$
| $5$

For example, after $A=0,B=1$, <edge> $AB$ is fixed crossing and the other six <edges> are unresolved, giving $1+6/2=4$. Setting $C=0$ fixes $BC$ crossing and $AC$ noncrossing, leaving four unresolved <edges>: $2+4/2=4$. Setting $C=1$ instead fixes $AC$ crossing and $BC$ noncrossing, giving the same <conditional expectation>.

\Image[/conditional-expectations-choice-ledger.png]
{title=Conditional expected cut values along every chosen branch}
{description=At each step, both candidate values are computed by the <conditional expectation cut formula>. The highlighted cell is chosen; ties choose zero. Below, the retained <conditional expectation> follows $3.5,3.5,4,4,4,5$, starting before any label is fixed. The last value is the actual size of the resulting <cut of a graph>, rather than an average over remaining choices.}

The final labels are $(0,1,0,0,1)$, so the two sides are $\{A,C,D\}$ and $\{B,E\}$. The five crossing <edges> are $AB,BC,DE,EA,BD$; $AC,CD$ do not cross. This exceeds $m/2=3.5$, and hence also the rounded-up guarantee of four <edges>.

It is not a <maximum cut>. Labels $(0,1,1,0,1)$ cross all <edges> except $BC$, giving six. Seven are impossible because the <triangle in a graph> $ABC$ cannot have all three <edges> crossing a two-sided <cut of a graph>. An independent enumeration of all $2^5=32$ complete label assignments gives the following distribution, counting an assignment and its label-swapped counterpart separately:

|| Size of <cut of a graph>
|| Number of label assignments

| $0$
| $2$

| $1$
| $0$

| $2$
| $2$

| $3$
| $12$

| $4$
| $10$

| $5$
| $4$

| $6$
| $2$

| $7$
| $0$

The weighted sum is $112$, so the average is $112/32=3.5$, agreeing with <linearity of expectation>. Choosing $C=0$ in the earlier tie discards the remaining size-six completion while preserving the average of four. The method protects an <expected value> guarantee; it need not preserve the best possible completion.


 Conditional expectations cut example (source code)