This paper explores gender differences across the abilities of Junior (15–17 year old) and Senior (17–19 year old) students in terms of solving graph problems. As a basis to our assessment, we look at the graph tasks from the Slovak Bebras competition in 2012 to 2017 across both Junior and Senior categories. In our earlier research on this topic, we introduced a new method of categorising graph problems. This was based on an in-depth analysis of the various problem types aimed at 8–15 year old students, whereby a set of indicators were defined to predict whether a task was more likely to be successfully solved by girls or boys. In this paper, we apply the new categorisation onto graph tasks aimed at Junior and Senior students with an aim to verify whether the same predictors of girls’ and boys’ success remain valid. A qualitative analysis indicates that our categorisation of graph tasks is suitable for Junior and Senior categories with minor adaptation only. As a result of a subsequent quantitative analysis, we find a significant difference in the solution success rates between girls and boys in 38 out of 65 analysed graph tasks. In 35 tasks boys were significantly more successful and these were tasks with an overall lower success rate. Furthermore, a few tasks with contradictory results concerning girls’ and boys’ solution success were identified. We selected one of these tasks where a higher error tendency in older students was apparent, and further analysed it together with the students themselves (15–19 years old) in order to better understand the methods used by them while solving this task. Our findings can be used to enable authors of task sets and lesson plans to define problems in a manner that will minimize gender success differences such as the ones described in this study.