$[$C Program$]$ a Reductions and Boolean Satisfiability I $($Split graphs recognition$)$ Boolean satisfiability $($SAT$)$ is$,$ as far as Computer Scientists know, a hard problem. We will define precisely what we mean by this later on in the course. This problem is defined as follows: The input is a collection of m clauses over n boolean variables X$1,$ X$2,...$ Xn$.$ Each clause is a disjunction of some of the variables or their complements. The problem consists in answering the question $"$Is there a way to assign truth values to each variable that makes every clause of the instance TRUE? For instance, here is an instance of SAT made of $4$ clauses over $3$ variables: $1.$ XV X$32.$ XV XV X$33.$ X$2$ X$34.$ X$3$ Equivalently, you could think of this instance as the single boolean expression $($X$1$V X$3)($XVX$2$ V X$3)($X$2$ V X$3)$ A X$3$ There are many other problems whose level of difficulty is similar to that of Boolean Satisfiability, and this problem has attracted a lot of research. So while the problem is difficult to solve in general, a number of tools to solve instances of the problem have been developed $($see the Wikipedia page for details and links$).$ We can take advantage of these tools to solve other problems using reductions. In this question, we will look at the problem of determining whether or not a graph is a split graph. A graph G $=($V$,$ L$)$ is a split graph if we can partition its vertex set V into two subsets V$1,$ V$2$ such that V $=$ V UV$2,$ Vin V$2=\%,$ every two vertices of Vi are connected by an edge $($Vu E V$1,$ VW $$ V$1,\{$v$,$ w$\}$ E$)$ and no two vertices of V$2$ are connected by an edge $($Vv E V$2,$ VW E V$2,\{$v$,$w$\}$ &E$).$ For instance, the following graph is a split graph, where the vertices of Vi are colored Red, and the vertices of V$2$ are colored Blue. B$3$ B$4$ B$5$ R$1$ R$2$ B$2$ R$3$ B$6$ RO $$ B$1$ R$41.(3$ points$)$ Show how to reduce a arbitrary instance of the split graph recognition problem into an instance of Boolean Satisfiability $($SAT$).$ Ilint: you will want to introduce a single variable for each vertex of the graph. $2.[1$ point$]$ Write the collection of clauses you would get for the following graph: $3.[2$ points$)$ What is the length of the instance of SAT that your algorithm generates, as a function of the number n of vertices, and the number m of edges of the input graph G$?4.[3$ points$)$ Explain briefly why, if an input graph is a split graph, then there is a way to assign values to the variables in the instance of SAT that makes every clause TRUE. $5.(3$ points$)$ Explain briefly why, if there is a way to assign values to the variables in the instance of SAT that makes every clause TRUE, then the graph used to generate the instance must be a split graph. Show how you would determine which vertices of G belong to which of the two subsets of V$.$