# edge-partitioning a strongly connected 17-graph into four 4-connected 17-graphs

Is this possible? I have a 4-connected 17-graph and am wondering whether there are another 3 like it that can be put together to make its complement. My current 4-connected example is here

-
By "like it" do you mean the other graphs should be isomorphic, or simply that they should be 4-connected (on the same nodes) and disjoint? I think you are trying to edge-partition the complete graph $K_17$ with isomorphic copies of the given example. I'd guess it's easier to work computationally with the adjacency matrix. – hardmath Jan 26 '11 at 0:38
Complement with respect to what? – mjqxxxx Jan 26 '11 at 0:39
I doubt it's $K_{17}$ he's partitioning. I'm guessing it has something to do with the $17\times 17$ challenge. – mjqxxxx Jan 26 '11 at 0:40
@mjqxxxx: The phrasing is curious, but if we take "edge-partitioning" in the subject line as the dictum, then arithmetic shows the union of the four "4-connected" graphs (on 17 nodes) must be the complete graph on 17 nodes. – hardmath Jan 26 '11 at 3:01
@hardmath: You're right... I stand corrected. So now that we know the question, what's the answer? – mjqxxxx Jan 26 '11 at 4:16

Clearly you've decomposed $K_{17}$ into eight disjoint 17-cycles, any two of which would combine to give a regular subgraph of degree 4 with minimum cut set of size 4, so in that sense 4-connected. However it is not clear to me whether this can give four isomorphic subgraphs. Are you still interested in the original question whether four copies of the given example will cover $K_{17}$? – hardmath Jan 26 '11 at 15:24