Logical thinking of students should be enhanced at all levels of their studies. There are many possibilities how to achieve it. In the paper one possible way within the subjects “Discrete Mathematics” and “Discrete Methods and Optimization” dealing with graph theory and combinatorial optimization will be presented. These mathematical disciplines are powerful tools for teachers allowing them to develop logical thinking of students, increase their imagination and make them familiar with solutions to various problems. Thanks the knowledge gained within the subjects students should be able to describe various practical situations with the aid of graphs, solve the given problem expressed by the graph, and translate the solution back into the initial situation. Student engagement is crucial for successful education. Practical tasks and puzzles attract students to know more about the explained subject matter and to apply gained knowledge. There are an endless number of enjoyable tasks, puzzles and logic problems in books like “Mathematics is Fun”, in riddles magazines and on the Internet. In the paper, as an inspiration, four puzzles developing logical thinking appropriate to be solved using graph theory and combinatorial optimization will be introduced. On these puzzles of different level of difficulty the students’ ability to find out the appropriate graph-representation of the given task and solve it will be discussed as well. The author of the paper has been prepared with her students various multimedia applications dealing with objects appropriate to subject matter for more than 15 years. In the paper we also discuss a benefit of multimedia applications used as a support of subjects “Discrete Mathematics” and “Discrete Methods and Optimization”.