Простой:
Я вижу, что вы довольно сильно изменили флажок, чтобы он напоминал вершину, но теперь он всегда будет черным эллипсом, потому что вы явно задали «Fill»:
<Ellipse x:Name="ellipse" Fill="Black" Margin="0" Stroke="Black" Width="Auto"/>
Вместо этого используйте TemplateBinding, который будет изменять заливку всякий раз, когда вы устанавливаете свойство background для флажка:
<Ellipse x:Name="ellipse" Fill="{TemplateBinding Background}" Margin="0" Stroke="Black" Width="Auto"/>
и измените декларацию флажка на:
<CheckBox x:Name="chkVertex" Content="CheckBox" Template="{DynamicResource CheckBoxControlTemplate1}" Background="Red"/>
Теперь вы можете изменить цвет в выделенном коде в любое время, используя:
chkVertex.Background = //whatever color you like
или вы можете связать свойство Background флажка в xaml со свойством background вершины, чтобы иметь более чистый подход.