Is there more than 1 way to make a 17-node graph such that there are no 4-cycles and each node has at least four edges? I'm working on the 17x17 challenge, and this sub-problem has come up. I have one solution to this problem that you can see here:

For some complex reasons (that I can elaborate on if needed) I know that this graph is unique if I add the following constraint: There has to exist a subset of at least 6 5 nodes that are not connected to each other and are not individually part of a 3-cycle. In the graph above, any 5-set of pink nodes satisfies this constraint. What I do not know is if it is still unique when I remove this extra constraint.
I'm coming from a CS background so I may be missing something basic from a graph theory perspective. Any references that may help me either prove that this is the case, disprove it by producing one or more different graphs or (even better) by producing all possible alternative solutions would be deeply appreciated.
EDIT: On closer examination, it seems the graph contains a double Hamiltonian circuit that uses every edge. No idea if this is relevant. [not interesting]
 A: I don't have the reputation to comment here, but that last example of a circulant graph by Gerry has plenty of 4-cycles... e.g., take 1,5,6,2. Sorry I don't have anything constructive to answer.
A: I don't know whether this one is different from the one you have, but one way to make such a graph is to start with a (convex) 17-gon (so there are your 17 nodes, and two edges at each) and then draw an edge connecting each vertex to the ones four vertices away in either direction (two more edges at each vertex, making 4 in all). 
EDIT: Oops! My thanks to those who pointed out the error here, and my apologies for posting this incorrect answer. 
A: Here's an idea.  Start with a list of all the 4-subsets of vertices and a complete graph.  Start removing edges greedily to break many 4 cliques while keeping the degrees high.  At some point you will have a fairly dense graph with a hopefully short list of 4-cycles remaining.  You can then try nongreedy or exhaustive algorithms to produce a subgraph with no 4 cycles.
Gerhard "Ask Me About System Design" Paseman, 2011.01.25
