[phalf]

A while back I interviewed with a networking company in the bay area and one of the things the interviewer asked me do was to devise an algorithm to walk the fully connected graph without visiting any edge twice if possible. Was a nice problem to discuss, he moved me along nicely in my thought process and we eventually reached a recursive solution. So the length of this walk is basically this formula.

He told me they are using such an algorithm in some of their products and he picks the brain of potential hires to see if they find a more elegant way of doing so. Left a great impression, he really cared about thought processes and communicating! (I didn't end up taking the job for reasons unrelated to the company or the offer.)

[dcanelhas]

Sounds like a traveling salesman problem... Perhaps if you look at a dual graph where the edges are collapsed into nodes and the nodes are stretched out to become edges? Then the problem statement of "visiting each city only once" might become equivalent.

[a_e_k]

I assume that's only possible in the general case for an odd number of vertices?

A fully connected graph with an even number of vertices will have odd degrees for all of them, and so can't have an Eulerian path.

[phalf]

I could be mixing things up here, it's been too long ago. I think this was about a directed graph, so the number of edges is actually N^2 and your walk roughly of that length.

[hgsgm]

/r/2IsNotEven

[bibanez]

To walk a fully connected graph with a prime number of vertices you can walk first to x+1, then x+2 then x+3 etc. edges by looping around. This a fun special case to prove (basically if you loop by x+i where i coprime to n, it loops after visiting all the vertices, and if n is prime every i is coprime to it)

[sorokod]

Isn't the length of the walk the number of edges?

[vince3455]

Whenever you visit a node you need one edge to walk in and one to walk out, except for the first and last node. So all K_n with even n , you can walk all the edges. For odd n, you lose one edge per node, except for 2 of them

[JadeNB]

I think the parent was agreeing with you, but saying that the number of edges on the fully connected (usually called complete) graph on n vertices is 1 + 2 + 3 + … + n = n(n + 1)/2.