Vertex Cover. Given an undirected graph $G=(V,E),$ a Vertex Cover is a set of vertices $V^{\text{'}}$subeV

such that every edge einE is incident on $($touches$)$ some vertex in $V^{\text{'}}.$

$($a$)$ Write the vertex cover problem as a linear program. The variable assignments need not be integral.

$($b$)$ Design an instance of the vertex cover problem where your LP outputs a non$-$integral solution. Your

instance must use $3$ nodes or less.

NP and EXP. Prove that NP sube EXP.