hello all ,

There are two problems. I need a help on in discrete mathematic. which are:

1) A hole in a graph is an induced cycle of size 5 or more. An antihole is the complement of a hole. In this problem you are to consider the complements of odd cycles of size 5 or more.

Are odd antiholes (of size 5 or more) circular-arc graphs? Prove your answer. If no, argue that a circular-arc model cannot exist; if yes, describe how to construct a circular-arc model. Your answer must apply to ALL odd antiholes (not just 5-antiholes, or any specific size).

2)

a) Give a graph for which the algorithm does not find a maximum size independent set.

b) Give the set the algorithm finds and explain how this arises.

c) Give a maximum independent set of a larger size.

Algorithm for that use in the second question is : Greedy Maximum Independent Set.

Given a graph G = (V, E), find a maximum size independent set I.

1. Choose a vertex x that has minimum degree to include in I.

x is our Greedy Choice.

2. Remove x and any neighbors of x from G.

3. Repeat 1 and 2 in the remaining graph. (Our optimal solution must include a maximum size independent set in the remaining graph.)

if anyone are able to help me on that . please let me know . thank’s