There have been numerous studies exploring the applications of graph theory in traffic management, often finding ways to reduce traffic congestion and make traveling more efficient. Such studies will be beneficial when applied to heavily congested areas such as España Boulevard, one of the busiest thoroughfares in Manila. This paper aimed to optimize the road map of España Boulevard using graph theory. The current road map of España Boulevard was represented as a directed graph and subjected to the mutation method of edge removal, wherein an edge is removed in each mutation based on a computed fitness function, F(G), which depicts better efficiency at lower values. Edges were removed until the graph got disconnected, which was tested using the Floyd-Warshall algorithm. The 28th mutation resulted in a minimum F(G) value of 144.4; this is a 50.18% decrease from the F(G) of the original graph, which is 290. After the 28th mutation, the removals resulted in an increase in the F(G). Consequently, the final mutation resulted in an F(G) of 311.89, which characterized a less efficient graph. This study was able to apply graph theory concepts to optimize the España Boulevard road map using the mutation method, minimizing its F(G) by at most 50.18%. For future studies, the practicality of the alternate road map may be tested in simulations to examine its efficiency when other factors, such as traffic volume, are introduced.