There exist a path of length $⌈ d (G)⌉$ for every graph $G$

1 Unweighted Graph

$G$ is a simple graph, then $d (G) = \frac{2 e ( G )}{∣ G ∣}$ be the average degree of a simple graph.

Lemma1

If $G$ is a connected graph, then it contain a path of length $min (2 δ (G), ∣ G ∣ - 1)$ , where $δ (G)$ is the minimum degree of $G$ .

The above lemma is Exercise 1.7. in Graph Theory by Diestel.

Lemma2

Every graph $G$ has a component $H$ , such that $d (H) \geq d (G)$ .

Proof

Fact: If $x_{i}, y_{i} > 0$ and $\frac{x _{i}}{y _{i}} < t$ for all $1 \leq i \leq k$ , then $\frac{\sum _{i = 1}^{k} x _{i}}{\sum _{i = 1}^{k} y _{i}} < t$ . Assume the lemma is false, then consider all it’s components $H_{1}, \dots, H_{k}$ , $d (H_{i}) = \frac{2 e ( H _{i} )}{∣ H _{i} ∣} < d (G)$ , then $d (G) = \frac{\sum _{i = 1}^{k} 2 e ( H _{i} )}{\sum _{i = 1}^{k} ∣ H _{i} ∣} < d (G)$ , a contradiction.

Theorem3

A simple graph $G$ must contain a path of length at least $d (G)$ .

Proof

Proof by induction. It is true for graph with 1 vertex. Assume it is true for all graphs with $k$ vertices, $k < n$ . Consider graph $G$ of $n$ vertices. If the graph has more than 1 component, then we use Lemma 2 and show there exist a subgraph $H$ with strictly smaller number of vertices, such that $d (H) \geq d (G)$ , and just apply the induction hypothesis.

Otherwise, the graph is connected. If there exist a vertex $v$ with degree at most $\frac{1}{2} d (G)$ , we can remove it, and $d (G - v) \geq d (G)$ , then by inductive hypothesis, in $d (G - v)$ there will be a path of length at least $d (G)$ . If there is no such vertex. then we must have $δ (G) > \frac{1}{2} d (G)$ . By Lemma 1, we have it has a path of length $min (2 δ (G), ∣ G ∣ - 1)$ . $2 δ (G) \geq d (G)$ and $d (G) \leq ∣ G ∣ - 1$ , thus it contain a path of length at least $d (G)$ .

2 Weighted Graph

Can we generalize this problem to weighted graphs? $G = (V, E)$ , $(G, w)$ is a weighted graph, where $w : E \to R$ . Define the average weighted degree of graph $G$ to be $d_{w} (G) = \frac{2 \sum _{e \in E} w ( e )}{∣ G ∣},$ and the minimum weighted degree $δ_{w} (G) = e \in E min {w (e)} .$ If $P$ is a path, then the weight of the path is $W (P) = \sum_{e \in P} w (e)$ . What can we say about the path with maximum weight? It is easy to prove that there is a path of weight at least $δ_{w} (G)$ .

Theorem4

For a weighted graph $(G, w)$ , there exist a path of weight at least $δ_{w} (G)$ .

Proof

Consider the longest path $v_{1}, \dots, v_{n}$ . Claim: $w ({v_{i}, v_{n}}) \leq w ({v_{i}, v_{i + 1}})$ for all $i$ . Assume not, then the path $v_{1}, \dots, v_{i - 1}, v_{i}, v_{n}, v_{n - 1} \dots, v_{i + 1}$ would be heavier, a contradiction. Therefore we have $δ_{w} (G) \leq {v_{i}, v_{n}} \in E \sum w ({v_{i}, v_{n}}) \leq i = 1 \sum n - 1 w ({v_{i}, v_{i + 1}}) = W (v_{1} \dots v_{n})$

However, we want something stronger, say instead of $δ_{w} (G)$ , can it be $d_{w} (G)$ ? I have a proof but it uses a difficult lemma.

Definition5

A perfect path double cover (PPDC) for graph $G$ is a set of paths, such that every edge is covered exactly two times, and every vertex is the end point of exactly two of the paths.

Note a PPDC for a graph with $n$ vertices is a set of $n$ paths.

Lemma6

Every simple graph has a perfect path double cover.

The lemma is proven by Hao Li in 1990.

Now we conclude with the theorem that eats up all the above special cases.

Theorem7

For a weighted graph $(G, w)$ , there exist a path of length at least $d_{w} (G)$ .

Proof

Consider a PPDC of $G$ with $n$ paths $p_{1}, \dots, p_{n}$ . $\sum_{i = 1}^{n} l (p_{i}) = n d_{w} (G)$ , by pigeonhole principle, at least one of the path has length at least $d_{w} (G)$ .

I wonder if there is a simpler proof of the fact, so no high machinery like PPDC are involved.

All these results are of course, already known. Frieze, McDiarmid and Reed have solved it in 1992. It is a 10 page proof, and thanks to Charalampos who provided it in the comment. The proof for PPDC only used 2 pages, so this would be an easier proof.

How do we find such a path? PPDC can be computed in $O (m Δ (G))$ time, so we actually have a polynomial time algorithm for this.

This give us a fun problem.

Problem8

Prove that for every weighted multigraph with no self loop, if it has $M$ edges and the largest set pairwise non-parallel edges has $m$ edges, then there exist a path of weight at least $\frac{d _{w} ( G )}{M - m + 1}$ .

Posted by Chao Xu on 2013-01-30.

Tags: graph theory.

There exist a path of length ⌈d(G)⌉ for every graph G

1 Unweighted Graph

2 Weighted Graph

There exist a path of length $⌈ d (G)⌉$ for every graph $G$