Graph theory is an advanced subject of mathematics that can be utilized to resolve issues in science. Graph coloring is one of the most well-known problems for determining the color of the map. The map that will be colored here is one of the 21 sub-districts that cover the Medan regency. In order to color the map, a graph model of the map must first be created. The use of a greedy algorithm is one technique to find a graph's minimal color. The dual graph with 21 vertices and 45 edges will be what we extract from the map. Based on the greedy method that has been used, just four colors—blue, green, red, and yellow—are found as the smallest number of colors, with each city that borders another having a distinct color. The Python computer language is used to get the map coloring results using the greedy technique.