Grafteori/ Kombinatorik trianglar i en graf
Låt G vara en connected planar graf. Jag har visat att den inte har en triangulation. Men vill ändå se om det finns någon triangel i grafen? Några allmänna tips hur man kan gå tillväga? Jag har antalet faces, vertices och edges.
Den informationen räcker inte. Det finns t.ex. planara grafer med 2 sidor (3 om omgivningen räknas som sida), 7 kanter och 6 hörn som har en triangel, och andra sådana som inte har det.
Jag kom på att jag glömde skriva att jag också vet ordningen hos the vertices. En har ordning 5, 7 med grad 3 och 2 med grad 4. Blir det någon skillnad?
Lägg in en bild av uppgiften. Det är väl onödigt att vi skall sitta här och gissa, och gissa fel eftersom vi inte har all relevant information?
Denna uppgift var en del av e examinerande inlämning.
