Menu
A graph of even order is called path-pairable if, for any pairing of its vertices, there exist edge-disjoint paths connecting the paired vertices. Extremal problems for path-pairable graphs with restrictions on the maximum degree will be considered. In particular, let \(f(n, k)\) denote the minimum number of edges in a path-pairable graph of order \(n\) and maximum degree \(k\). Exact values of \(f(n, k)\) are determined for \(k = n-1, n-2,\) and \(n-3\).