Jaka jest najmniejsza liczba krawędzi jaką trzeba usunąć z grafu \(\displaystyle{ K _{3,5}}\) aby powstał graf planarny. Swoją odpowiedź uzasadnij.-- 30 cze 2009, o 13:32 --Nie jestem pewien ale chyba znalazłem rozwiązanie problemu.
Graf \(\displaystyle{ K _{5,3}}\) nie zawiera trójkątów (czyli cykli długości 3) więc każdy jego podgraf spełniać będzie nierówność \(\displaystyle{ K \le 2W-4=2 \cdot 8-4=12}\). Graf \(\displaystyle{ K _{5,3}}\) posiada 15 krawędzi więc 15-12=3 więc tyle krawędzi trzeba usunąć.