Problem of the Day #39

POTD January 13, 2023
Consider a graph with the following properties:

1. Every pair of vertices has a path between them with at most 2024 edges.
2. Every pair of vertices has a path between them with an even number of edges (you can visit the same vertex and travel across the same edge multiple times).

Find the smallest k such that every pair of vertices has a path with an even number of edges which is at most k.