TU Wien:Diskrete Mathematik für Informatik VU (Drmota)/Übungen WS20/Beispiel 9

A graph $H=(V',E')$ is an induced subgraph of $G=(V,E)$, if V' $\subseteq$ V and any edge in G connecting two vertices a,b in V' is in E'. Let G be a connected simple graph that does not have path or cycle with four vertices as an induced subgraph. Show that G has a vertex adjacent to all other vertices.

(Hint: consider a vertex of maximum degree.)

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

Lösungsvorschlag von 80.110.247.152

--80.110.247.152 22:46, 21. Okt. 2020 (CEST)

Mein Vorschlag ist, vor allem die Angabe zunächst ein bisschen verständlicher zu formulieren. In meinen Worten würde sie ungefähr so aussehen:

"Let G be a connected simple graph. All possible induced subgraphs of G have no cycle with more than 3 vertices and no path with more than 3 vertices. Show that the base graph G (not its subgraphs) has a vertex adjacent to all other vertices (a so called "universal vertex" or "dominating vertex")."

G ist also definiert durch die Eigenschaften seiner möglichen induced subgraphs. Weiters möchte ich hier die Kleinigkeit anmerken dass einer der möglichen subgraphs von G gleich G selbst ist, weil das subset von G aus ganz G bestehen kann.

Nun soll man zeigen dass dieser Graph G einen Vertex besitzt der mit allen anderen adjacent ist.

Lösungsvorschlag:

Start with vertex u and assume u has maximum degree. If we add one vertex v, the assumptions that u still has maximum degree, no cycle in subgraphs with more than 3 vertices and no path in subgraphs with more than 3 vertices are all met. If we add any further vertices to u directly, and ONLY to u (e.g. not connecting v1 with v2, but only v1 with u and v2 with u), the assumptions are never contradicted, so everything is still OK. The first vertex which is connected not directly to u will either lead to a triangle or will contradict the assumptions: If not a triangle, a path with more than 3 vertices is introduced. Therefore, only a triangle or a star with an arbitrary amount of leaves is possible for the graph G.