= Solution
Use <vertices> $1,2,3,4,5$. Reading each symmetric off-diagonal pair once gives the <edge set>
$$
\boxed{E=\{12,15,23,25,34,35,45\}.}
$$
Here $ij$ abbreviates the undirected <edge> $\{i,j\}$. The diagram displays these seven <edges> and no loops. The displayed square <matrix> is an <adjacency matrix> in the usual terminology: its two indices both label vertices. A vertex-edge <incidence matrix> would instead have one index for vertices and one for <edges>. This explains how the source's node-node terminology is being read.
\Image[/past-exam-of-the-integer-programming-course-of-the-university-of-oxford/2011-graph-and-maximum-forest.png]
{title=The graph and its maximum-weight forest, including the isolated fourth vertex}
{description=Original drawing. The left panel shows all seven edges. The right panel shows only the three edges selected for the maximum-weight forest, with their weights; vertex four remains isolated.}
Back to article page
