Write

ij

for the undirected edge

{i, j}

. At the root of the branch and bound search, the minimum spanning tree on

{2, 3, 4}

{24, 34}

of cost

6 + 4 = 10

. The cheapest edges incident to vertex one are

12, 14

, of cost

3 + 7 = 10

. The root lower bound is therefore twenty, attained by

T_{0} = {12, 14, 24, 34} .

(1)

It is not a tour: vertex four has degree three and vertex three degree one.

A tour must omit at least one edge from

{14, 24, 34}

, since its degree at vertex four is two. Partition tours according to the first omitted edge in that ordered list. This gives three disjoint, exhaustive children, retaining included and excluded edges when recomputing the one-tree relaxation:

Exclude $14$ . The incident pair is now $12, 13$ of cost twelve, and the other spanning tree still costs ten. The resulting one-tree ${12, 13, 24, 34}$ is a tour, so it supplies an incumbent solution of cost $22$ .
Include $14$ and exclude $24$ . The other spanning tree must be ${23, 34}$ of cost fourteen; the cheapest permitted incident pair costs ten. The lower bound is $24 \geq 22$ , so prune this child.
Include $14, 24$ and exclude $34$ . The spanning tree must be ${23, 24}$ of cost sixteen; the incident pair again costs ten. The lower bound is $26 \geq 22$ , so prune this child too.

All tours belong to one of the three children, and no remaining child can improve the incumbent. Therefore

1 \to 2 \to 4 \to 3 \to 1 is optimal, with cost 3 + 6 + 4 + 9 = 22.

(2)

The branching rule is motivated by a violated tour degree equation, rather than by an arbitrary costly edge. This is degree branching with a one-tree bound.