# Problem with graph

We have the following graph:

I want to find a minimal vertex cover. I thought that the set $C^\star=\{1,2,3,7\}$ is a minimal vertx cover. Is this correct? How could we prove it?



Then I want to find a vertex cover using the following approximation algorithm

C <- 0
while E ≠ 0 do
choose e = (u,v) ∈ E arbitrary
C <- C U {u,v}
G <- G - {u,v}
return C


I have done the following: Suppose we start with e=(1,4) then C={1,4} and the graph is the following: Then when we choose e=(5,7) we have C={1,4,5,7} and the graph will look as follows: Then we can choose e=(2,3) and then we have C={1,2,3,4,5,7} and the graph will be: Have we finished now? Is a minimal vertex cover the set $C=\{1,2,3,4,5,7\}$ ?

Does this mean that no matter which edge we choose at each step the minimal vertex cover will contain $6$ vertices?



After that I want to find a maximal independent set of vertices and a maximal clique. Could you give me some hints how we could find them?

## 1 Answer

I thought that the set $C^⋆=\{1,2,3,7\}$ is a minimal vertex cover. Is this correct? How could we prove it?

No, because it does not cover all edges (in particular, none of the edges $\{4, 5\}, \{5, 6\}, \{4, 6\}$ are covered by any vertex in $C^*$).

Have we finished now? Is a minimal vertex cover the set $C=\{1,2,3,4,5,7\}$? Does this mean that no matter which edge we choose at each step the minimal vertex cover will contain $6$ vertices?

Yes, you've correctly implemented the greedy $2$-approximation algorithm. It is not minimal though: observe that $C$ has a subset $\{1, 3, 4, 5, 7\}$, which is still a vertex cover. So this greedy algorithm is not guaranteed to be optimal.

After that I want to find a maximal independent set of vertices and a maximal clique. Could you give me some hints how we could find them?

As a general heuristic, try a modified greedy algorithm. When picking vertices, don't just pick any random one; try picking the one with the lowest (or highest) degree. Then remove it (and anything else that we know is safe to remove) from the graph and repeat.

• So, is a minimal vertex cover the set $C^\star=\{1,3,4,5,7\}$ ?  For the maximal independent set of vertices, is it maybe $\{1,5,6\}$ ?  Is maybe the following a maximal clique? $\{1,2,3,4\}$ ? – Mary Star Aug 12 '16 at 8:41
• Yes. No, since $\{5, 6\}$ is an edge in the graph. No, since $\{3, 4\}$ is not an edge in the graph. – Adriano Aug 12 '16 at 8:45
• Just show that if you try to remove any single vertex from $C^*$, some edge doesn't get covered. Yes, $\{1, 5\}$ is a maximal independent set (in fact, it's also maximum). Yes, $\{4, 5, 6, 7\}$ is a maximal clique (in fact, it's also maximum). – Adriano Aug 12 '16 at 8:55
• You used $4$ colours, so the chromatic number is at most $4$ (can you see why the chromatic number could never be $3$?). You provided a Hamiltonian cycle, but not an Eulerian circuit (for example, you did not visit the edges $\{1, 3\}$, $\{2, 5\}$, and so on). – Adriano Aug 12 '16 at 9:20
• That's correct. – Adriano Aug 12 '16 at 9:32