Create a circuit based on a graph Let's say I have a graph,

and from this graph I want to create a circuit $K$ whose inputs can be set so that $K$ outputs true iff the graph has an independent set of size $\ge2.$
I've seen some decent stuff on the interent / youtube about how to go about this. But I was wondering if there is a standard set of steps one should follow on how to do this.
 A: Here is a circuit for computing whether or not a graph on 6 vertices has a traingle. Note that the inputs are the edges of the graph, and are assumed to be boolean (1 indicating that an edge is present, and 0 o.w.) The edges are fed into the "gates" in the bottom. Each gate represents a subgraph containing the edges in it. In this case you are considering complete/empty subgraphs, so the "gates" will and together the edge bits. The circuit below can be simplified, but in general, it will have on the order of $\dbinom{n}{k}$ gates for computing whether or not a graph has a complete/empty subgraph of order $k$.

note that the bottom gates should be "or'd" together, I left this out for illustrative purposes.
Here is a circuit for computing whether or not a graph on 6 vertices has a complete/empty graph on 4 vertices

as you can imagine, these circuits get messy pretty quickly.
If you are interested in actually building circuits for this task, then I recommend checking out "Binary Decision Diagrams" or their closely related 'cousin', "Zero-Suppressed Binary Decision Diagrams." These are basically "Dynamic Programming" circuits, for lack of a better word. They exploit the repeated substructure of larger un-reduced circuits and can compress quite well for most practical purposes. They are used extensively in database design.
