Operationer på en graf

Jag misstänker att det går att reducera $K_n$, $n\geq 4$ till grafen $K_{n-1}$ med ett extra hörn och en kant. I exemplet du ger reduceras $K_4$ till $K_3$ (en triangel eller 3-cykel) plus ett extra hörn och en kant. Om det stämmer kan vi få $n-4+4=n$ kanter genom att upprepa denna process.

Man kan aldrig uppnå ett träd (3 kanter) från $K_4$. Så $n$ kanter är bästa möjliga för $n=4$, behöver fundera på om detta är sant även för $n\geq 5$.

Så klart kan vi aldrig få $n-2$ kanter, eftersom en sammanhängande graf med $n-1$ kanter inte har några cykler. Vi kan heller inte nå en osammanhängande graf, eftersom en kant sådan att grafen blir osammanhängande om den tas bort (en "brygga") inte kan ingå i en cykel. Däremot kan en graf med $n$ kanter ha en 4-cykel, så vi måste visa att $n$ är bästa möjliga även för $n\geq 5$.

Återkommer med lite bevis av det jag påstår vid tillfälle.

Lemma 1. Antag att vi har en kant i en graf med egenskapen att om vi tar bort den så blir grafen osammanhängande. Då kan inte kanten ingå i någon cykel.

Bevis: Låt $e=\{v_1,v_2\}$ vara en sådan kant. Låt $G_1$ och $G_2$ vara komponenterna som uppstår när vi tar bort $e$. Varje väg mellan något hörn i $G_1$ och något hörn i $G_2$ måste gå via kanten $e$, annars skulle grafen inte bli osammanhängande om $e$ togs bort.

Men om det fanns en cykel $C=(v_1v_2\dots v_k)$ så skulle vi kunna gå från $v_1$ till $v_2$ genom att gå från $v_1$ till $v_k$, sedan till $v_{k-1}$, sedan till $v_{k-2}$, och så vidare tills vi når $v_2$. Men då är grafen inte osammanhängande om vi tar bort $e$, vilket är en motsägelse. Alltså kan $e$ inte ingå i någon cykel.

Lemma 2. Låt $G$ vara en graf med $n$ hörn och färre än $n-1$ kanter. Då är $G$ osammanhängande.

Lemma 1 ger att en graf som erhålls från processen beskriven i problemet med start i någon komplett graf $K_n$ måste vara sammanhängande, eftersom varje kant vi tar bort ingår i en cykel. Enligt lemma 2 måste den då ha minst $n-1$ kanter. Alltså är $n-1$ en undre gräns för det minsta antalet kanter vi kan få.

Lemma 3. För varje $n\geq 3$ kan $K_n$ reduceras till en graf med $n$ kanter genom att upprepat välja en 4-cykel och ta bort en av kanterna i cykeln.

Bevis: Notera först att om $n=3$ finns inga 4-cykler och grafen $K_3$ har 3 kanter, så det finns inget att visa. Antag därför att $n\geq 4$.

Kalla hörnen i $K_n$ för $v_1,v_2,\dots, v_n$. Fixera något hörn, säg $v_n$. Det går en kant från $v_n$ till var och en av de resterande $n-1$ hörnen. Hörnen $v_1,v_2,\dots,v_{n-1}$ bildar tillsammans grafen $K_{n-1}$. 

Välj 4-cykeln $(v_nv_1v_2v_3)$ och radera kanten $\{v_1,v_n\}$.

Välj sedan 4-cykeln $(v_nv_2v_3v_4)$ och radera kanten $\{v_2,v_n\}$.

Fortsätt på samma vis att välja 4-cykeln $(v_nv_iv_{i+1}v_{i+2})$ och radera kanten $\{v_i,v_n\}$ för alla $i=1,2,\dots,n-3$.

För att radera den sista kanten $\{v_{n-2},v_n\}$ kan vi t.ex. välja 4-cykeln $(v_nv_{n-2}v_{n-3}v_{n-1})$.

Vi har nu raderat alla kanter från $v_n$ förutom $\{v_n,v_{n-1}\}$. Det kvarstår en graf på formen $v_n-K_{n-1}$ som består av $K_{n-1}$ samt ett extra hörn $v_n$ och en kant $\{v_n,v_{n-1}\}$.

Om vi nu väljer ut $v_{n-1}$ och upprepar samma procedur som tidigare på hörnen $v_1,v_2,\dots,v_{n-2}$ får vi en graf på formen $v_n-v_{n-1}-K_{n-2}$.

Vi fortsätter proceduren tills vi når en graf på formen $v_n-v_{n-1}-\dots -v_4-K_3$:

Denna graf har $n$ kanter, vilket var det vi ville visa.

Det återstår att utröna huruvida vi kan uppnå $n-1$ kanter eller inte, för alla $n$. Inte säker på hur man kan visa det än. För $n=4$ är det enkelt att se att vi som bäst kan komma ner till 4 kanter, men det är inte uppenbart varför det inte finns någon smartare metod för högre $n$ som kan ta oss ner till $n-1$ kanter.

Snyggt att du såg en invariant hos transformationerna – $G$ förblir sammanhängande efter varje drag, vilket ger den nedre begränsningen $n-1$. Dessutom beskrev du en algoritm för att erhålla en graf med exakt $n$ kanter.

Det som saknas är, precis som du säger, huruvida det är möjligt att få en graf med exakt $n-1$ kanter.

Ett litet tips: Om du studerar de grafer som bildas efter varje drag, ser du att de alla har en viss egenskap gemensamt. Tex. för $n=4$, vad är det som hindrar dig från att fortsätta? Undersök fler värden på $n$ – ser du något mönster?

För att visa att $n$ är minsta möjliga antalet kanter så behöver vi visa att $n-1$ inte är möjligt. Om en graf med $n$ hörn har $n-1$ kanter kan den inte ha några cykler. Vi vill därför visa att vi inte kan radera alla cykler i $K_n$.

Det enda sättet vi når en graf utan cykler är om vi steget innan har en ensam 4-cykel kvar. Det tycktes inte vara möjligt att nå en ensam 4-cykel hur jag än försökte. Det gick att få en ensam 3-cykel kvar från $K_5$ och $K_4$ och ensam 5-cykel från $K_5$ när jag testade.

Låt säga att vi har en graf med en enda cykel som inte är av längd 4. Det är tydligt att vi aldrig kommer kunna radera en kant i den (för då måste nämligen ytterligare en cykel finnas, nämligen den av längd 4). Därav är kruxet att visa att vi kan eller inte kan uppnå en ensam 4-cykel.

Lemma 4. Antalet kanter i Lemma 3 är det minsta möjliga.

Bevis: Låt säga att vi har en cykel av någon längd $k$, $k\neq 4$. Om vi vill radera en kant i cykeln så finns det tre fall. Vår 4-cykel vi använder för borttagningen kan ha en, två, eller tre kanter gemensamt med $k$-cykeln. Observera att 4-cykeln kan ha tre kanter gemensamt med $k$-cykeln endast om $k\neq 3$, dvs. om $k\geq 5$.

Om 4-cykeln har en kant gemensam (svarta strecken) så måste det finnas en $k+2$ cykel i grafen. Raderar vi den genemsamma kanten försvinner $k$-cykeln men vi har kvar $k+2$-cykeln.

Om 4-cykeln har två kanter gemensamt (röda strecken) så måste det finnas en annan $k$-cykel i grafen. Raderar vi någon av de gemensamma kanterna  har vi kvar den andra $k$-cykeln.

Om 4-cykeln har tre kanter gemensamt (blåa strecken) måste det finnas en $k-2$-cykel. Tar vi bort någon av de tre gemensamma kanterna så har vi kvar $k-2$-cykeln.

Vi kan börja med att konstatera att det enda sättet vi kan bli av med alla cykler i en graf är om grafen har en ensam cykel kvar av längd 4. I alla andra fall gäller från ovan att vi har kvar cykler i grafen efter varje borttagning av en kant.

Men här kommer slutklämmen: Om $k$ är udda så kan vi bara radera en kant i en $k$-cykel om det finns en annan cykel med udda längd ($k+2$, $k-2$, eller $k$). Det betyder att vi aldrig kan bli av med alla udda cykler i grafen. Så det enda sättet vi möjligen kan få en ensam 4-cykel är därför om vi börjar med en graf utan udda cykler.

Eftersom alla $K_n$, $n\geq 3$ innehåller minst en udda cykel så är detta inte möjligt.

Alltså är $n$ det minsta möjliga antal kanter som kan uppnås.

Ett annat sätt att formulera samma påstående är följande (att $G$ alltid innehåller cykler av udda längd är ekvivalent med att $G$ är icke-bipartit):

Claim. $G$ kan aldrig vara bipartit efter något drag.

Bevis. Antag motsatsen. Uppenbarligen är $K_{n}$ inte bipartit, eftersom den alltid innehåller en triangel för $n \geq 3$. Det innebär att det finns en icke-bipartit graf $G$ samt en cykel $C_{4}$ i $G$, där borttagandet av en kant $e$ resulterar i en bipartit graf $G \setminus e$.

Per definition kan vi partitionera hörnen av $G \setminus e$ i två hörnklasser, $V_{1}$ och $V_{2}$, sådana att inga två hörn inom samma klass är grannar (definitionen av en bipartit graf). Notera att $C_{4} \setminus e$ är en stig av längd $3$ vilket innebär att dess ändpunkter måste tillhöra olika klasser.

Om vi nu adderar tillbaka $e$ ser vi att dess ändpunkter tillhör olika klasser, vilket betyder att $G$ är bipartit – en motsägelse! qed

Så om det vore möjligt att åstadkomma en graf $G$ med exakt $n-1$ kanter skulle vi per definition ha ett träd på $n$ hörn (eftersom vi tidigare bevisade att $G$ förblir sammanhängande efter varje drag). Men ett träd innehåller inga cykler, och därmed bipartit – en motsägelse.

Hade helt glömt bort att bipartita grafer var en grej. Kul problem, spenderade alldeles för mycket tid på att fnula på detta... det första som dök upp i huvudet när jag vaknade imorse, haha.

Ibland löser det sig när man får sova på saken... :D

Men bra jobbat ändå. Det tog mig längre tid än vad jag vill erkänna att inse varför en graf med $n-1$ kanter var omöjlig och dess anknytning till bipartita grafer när jag stötte på problemet hehe... :P