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
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
Ok, I've been able to decompose K17 into 8 2-regular subgraphs. Here's my solution:
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.