Matematické Fórum

Skrytý text:
Já bych to asi zkoušel nějak odhadnout - když třeba zvolím jeden vrchol a udělám z něj střed hvězdy o n-1 cípech takových, že hrany jsou orientovány od středu hvězdy (tj. všechny zbylé vrcholy spojím s vrcholem středu hranami s orientací od středu k vrcholu). Tím jsem udal n-1 hran, aniž bych spojil byť jen dvě nějaké komponenty dohromady, dokonce mezi žádnými dvěma vrcholy na okraji hvězdy nevede žádná orientovaná cesta. No a teď udám dalších n-1 hran tak, že z nich udělám kružnici, na které leží oněch (n-1) vrcholů na okraji hvězdy - hrany orientuju ovšem střídavě, tj. z každého vrcholu dvě šipky kružnice buď vycházejí, nebo do ní vcházejí (kromě případného lichého vrcholu v kružnici - do něj by případně jedna šipka vcházela a jedna vycházela). Teď n>=5, tedy na takové kružnici leží alespoň 4 vrcholy, to znamená alespoń dva vrcholy A1,A2 takové, do kterých šipky pouze vcházejí, a alespoň dva B1,B2 takové, ze kterých šipky jen vycházejí (až na hranu od středu hvězdy). Zřejmě mezi A1,A2, resp. B1,B2 nevede hrana, můžu tedy tyto dvě hrany přidat a stačí si rozmyslet, že jsem tím sice spojil nějaké vrcholy cestou, ale mezi žádnými dvěma vrcholy nevede orientovaná cesta tam i zpět - tedy max. možný počet komponent je roven počtu vrcholů a tedy n.