\Opgave 17 

a) Let x_e = 1 iff edge e is chosen. Moreover we use the
   terminology \delta(v) to denote all edges incident to a node v.
   This leads to the formulation

   maximize    \sum_{e \in E} x_e

   subject to  \sum_{e \in \delta(v)} x_e <= 1

               x_e \in {0,1}


b) x_e = 1/(n-1) is FEASIBLE since each node v \in V has
   (n-1) edges and thus

       \sum_{e \in \delta(v)} x_e = \sum_{i=1}^{n-1} 1/(n-1) = (n-1)/(n-1) = 1

   the objective function is z = n/2, since there are n(n-1)/2 edges.

   To prove that the solution is OPTIMAL, we find a dual solution
   with the same objective value. The dual problem is

   minimize   \sum_{v \in V} y_v

   subject to y_u + y_v >= 1     (u,v) \in E

              y_v >= 0            v \in V

   A feasible dual solution is y_v = 1/2 for all v \in V.
   This solution has objective value z = n/2, which proves the stated.

c) We have \sum_{e \in \delta(v)} x_e <= 1 for all nodes  v \in V

   Add all inequalities

      \sum_{v \in V} \sum_{e \in \delta(v)} x_e \leq \sum_{v \in V} 1 = n
 
   giving

      2 \sum_{e \in E} x_e <= n

   and thus  

      \sum_{e \in E} x_e <= n/2

   since the LHS is integral we may truncate the RHS.