\Opgave 14

Node packing: select the max number of nodes such that two nodes
              chosen may not be connected by an edge.

Introducting binary decision variables x_i to indicate if node i
is chosen we get the model

   max \sum_{i=1}^{n} x_i

   s.t. x_i + x_j <= 1         for all (i,j) in E
 
   x_i \in {0,1}

(a) As the graph is symetrical we may start by choosing
    node 1. Due to the definition we can then exclude 
    nodes 3,4,5,6. The remaining nodes 2 and 7 are connected
    by an edge, thus at most one of these can be chosen.
    This proves that no solution will contain more than
    two nodes.

(b) For all edges (i,j) \in E we have

        x_i + x_j <= 1       

    consider a triangle, e.g. spanned by the nodes (1,3,6)

        x_1 +   x_3         <= 1
                x_3 +   x_6 <= 1
        x_1         +   x_6 <= 1
      --------------------------
      2 x_1 + 2 x_3 + 2 x_6 <= 3

    divide by two and round down

        x_1 +   x_3 +   x_6 <= 1


    Now, consider 7 such inequalities obtained for the triangles
    (1,3,6), (2,4,7), (3,5,1) ...


        x_1 +   x_3 +   x_6 <= 1
        x_2 +   x_4 +   x_7 <= 1
        x_3 +   x_5 +   x_1 <= 1
        x_4 +   x_6 +   x_2 <= 1
        x_5 +   x_7 +   x_3 <= 1
        x_6 +   x_1 +   x_4 <= 1
        x_7 +   x_2 +   x_5 <= 1
     -----------------------------------------
      3 x_1 + 3 x_2 + 3 x_3 + ... + 3 x_7 <= 7

    Divide by 3 and round down, getting

      x_1 + x_2 + x_3 + ... + x_7 <= 2