• For a fixed degree M and number of vertices V = (M + 1) M^N, the Kautz graph has the smallest
diameter of any possible directed graph with V vertices and degree M. • All Kautz graphs have
Eulerian cycles. (An Eulerian cycle is one which visits each edge exactly once—This result follows because Kautz graphs have in-degree equal to out-degree for each node) • All Kautz graphs have a
Hamiltonian cycle (This result follows from the correspondence described above between edges of the Kautz graph K_M^{N} and vertices of the Kautz graph K_M^{N + 1}; a Hamiltonian cycle on K_M^{N + 1} is given by an Eulerian cycle on K_M^{N}) • A degree-k Kautz graph has k disjoint paths from any node x to any other node y. == In computing ==