Knoten v in längstem Pfad und Pfad der Länge [2/n] - 1

Question

Aufgabe:

Gegeben ist ein Graph G der Ordnung n. G ist zusammenhängend.

P sei ein Pfad der Länge

$$ \lceil n/2 \rceil - 1 $$

und U der längste Pfad in G.

Zu zeigen ist, dass es ein Knoten gibt, der in P und U enthalten ist.

Problem:

Mir fällt kein möglicher Ansatz ein, ich weiß nicht wie ich an die Aufgabe herangehen soll.

Sollte man per Induktion Zeigen, dass dies für alle n gilt?

Bisher konnte ich nur zeigen, dass gilt:

$$ n - k \geq \lceil n/2 \rceil \ \ \ \ \ \text{k = Anzahl der getroffenen Knoten in U} $$

Answer 1

Hallo,

ich denke, hier reicht ein Widerspruchsbeweis. Mal angenommen es existiert kein Knoten der in beiden Pfaden enthalten ist.

Dann entferne man alle Kanten, die nicht zu \(P\) oder \(U\) gehören. Man erhält zwei Graphen \(G_p\) und \(G_u\) mit folgender Größe bzw. Ordnung also Anzahl der Knoten:$$\begin{aligned}\left|G_u\right| + \left|G_p \right| &\le n\\\left|G_u\right| &\ge \left|G_p \right| \\\implies \left|G_p\right|&\le \left\lfloor\frac n2\right\rfloor \end{aligned}$$Jetzt muss man noch zwei Fälle unterscheiden:

1.Fall \(G_p\) ist offen, dann ist \(\left|G_p\right| = \left\lceil\frac n2\right\rceil\). Damit ist bereits gezeigt, dass so ein Graph mit einem ungeraden \(n\) nicht existieren kann. Für ein gerades \(n\) muss dann gelten$$\left|G_p\right| = \left|G_u\right| = \frac n2$$Wir betrachte nun die kürzeste Verbindung zwischen den beiden Graphen. Die längere Länge des Pfades \(P\) vom Verbindungsknoten von \(G_p\) zu \(G_u\) habe die Länge \(m_p\) und die kürzere \(n_p\). Genauso stellt man bei \(G_u\) die Längen \(m_u\) und \(n_u\) fest. Es gilt $$m_p \ge n_p \land m_p + n_p = \frac n2 \\ m_u \ge n_u \land m_u + n_u = \frac n2$$Jetzt kann man zeigen, dass der Pfad über die Knoten von \(m_p\) und über die Verbindungskante zu \(m_u\) länger sein muss als der Pfad \(U\). Das wäre dann ein Widerspruch. (Details überlasse ich Dir)

2.Fall \(G_p\) ist geschlossen, dann ist \(\left|G_p\right| = \left\lceil\frac n2\right\rceil - 1\). In diesem Fall ist \(m_p = \frac n2 -1\) und man kann man über die Verbindungskante zum Pfad \(U\), und hat so wieder einen Pfad, der länger ist als \(U\).

Gruß Werner