Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 1 down vote accepted

Ok, I've been able to decompose K17 into 8 2-regular subgraphs. Here's my solution:

K17 decomposed into 8 2-connected subgraphs

My method is as follows: Starting from any vertex, skip n, and draw an edge to the vertex you ended up at. Repeat the process from the new vertex until you return to your origin. Any complete graph of order 2x+1 can be decomposed into n subgraphs by repeating the above process for values of n from 0 to x-1.

There are many ways to pair the 8 sub-grids so that they become 4 isomorphic 4-regular ones. First choose a type of polygon you'd like to be dominant in your sub-grids. For instance with triangles, you can pair n=1 with n=2 (1/2), then 3/6, 4/8, and 5/7 (since n=7 in a 17-node graph is the same as n=10). Alternatively, you could also pair 2/4, 6/5, 7/3, 8/1. There are also two ways to pair if you're aiming for rectangles and pentagons, and I assume all the way up to octagons, for a total of 12 ways to combine.

share|cite|improve this answer
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
You're right. 1+2, 3+6, 4+8 are isomorphic but (I think) 5+7 is different. I am certainly still interested in the original question. – Alexandros Marinos Jan 26 '11 at 15:35
Maybe 5+7 is also; after all the 7-stride is the same as the 10-stride 17-cycle. These would at least share in the existence of lots of triangles, something your original example has fewer of (if my eyes can be trusted). – hardmath Jan 26 '11 at 16:21
I think you're right again! for 1/2, for every vertex, following the 1-stride edges gives you vertices linked by a 2-stride edge. Same for 2/4 and 3/6. This is true for 7/5 also, but for each vertex you must follow the 7-stride vertices and you find 5-stride linked vertices. So 1/2, 3/6, 4/8, and 7/5 all have 17 triangles each. – Alexandros Marinos Jan 26 '11 at 17:34
Turns out, it's even more interesting than that! When aiming for triangles, there is an alternative combination: 2/4, 6/5, 7/3, 8/1. And there are two ways to combine the subgraphs, whatever(?) type of polygon you're aiming for. I've worked it out for rectangles and pentagons, I'm sure it goes further than that. Trying a 16-gon, it seems to be the mirror of a triangle, so perhaps the limit would be an octagon. – Alexandros Marinos Jan 27 '11 at 15:31

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.