  We discuss the recently introduced concept of k-in-out graphs, and provide a
construction for k-in-out graphs for any positive integer k. We derive a lower
bound for the number of vertices of a k-in-out graph for any positive integer
k, and demonstrate that our construction meets this bound in all cases. For
even k, we also prove our construction is optimal with respect to the number of
edges, and results in a planar graph. Among the possible uses of in-out graphs,
they can convert the generalized traveling salesman problem to the asymmetric
traveling salesman problem, avoiding the "big M" issue present in most other
conversions. We give constraints satisfied by all in-out graphs to assist
cutting-plane algorithms in solving instances of traveling salesman problem
which contain in-out graphs.
