La teoría de grafos es una herramienta poderosa de representación y resolución de problemas, pero no está incluida en el currículo actual de los niveles escolares. En este estudio realizamos una propuesta didáctica basada en la teoría de grafos, para proporcionar a los estudiantes herramientas útiles y motivadoras para la resolución de problemas. Los participantes, que eran altamente hábiles en matemáticas, trabajaron en el coloreo de mapas, ciclos eulerianos, polígonos estrellados y otros temas relacionados. El programa incluyó seis sesiones en formato de taller y cuatro sesiones creativas donde los participantes inventaron sus propios desafíos matemáticos. A lo largo de la experiencia aplicaron una amplia gama de estrategias para resolver problemas, como buscar un patrón, estrategias de conteo o dibujar el grafo asociado, entre otros. Además, crearon como desafíos el mismo tipo de problemas planteados en los talleres. Concluimos que la teoría de grafos aumenta con éxito la motivación de los participantes hacia las matemáticas y permite la aparición y consolidación de estrategias de resolución de problemas.