The Art Gallery Guardian

There exist a path of length for every graph


1 Unweighted Graph

is a simple graph, then be the average degree of a simple graph.

Lemma1

If is a connected graph, then it contain a path of length , where is the minimum degree of .

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

Lemma2

Every graph has a component , such that .

Proof

Fact: If and for all , then . Assume the lemma is false, then consider all it’s components , , then , a contradiction.

Theorem3

A simple graph must contain a path of length at least .

Proof

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

Otherwise, the graph is connected. If there exist a vertex with degree at most , we can remove it, and , then by inductive hypothesis, in there will be a path of length at least . If there is no such vertex. then we must have . By Lemma 1, we have it has a path of length . and , thus it contain a path of length at least .

2 Weighted Graph

Can we generalize this problem to weighted graphs? , is a weighted graph, where . Define the average weighted degree of graph to be and the minimum weighted degree If is a path, then the weight of the path is . What can we say about the path with maximum weight? It is easy to prove that there is a path of weight at least .

Theorem4

For a weighted graph , there exist a path of weight at least .

Proof

Consider the longest path . Claim: for all . Assume not, then the path would be heavier, a contradiction. Therefore we have

However, we want something stronger, say instead of , can it be ? I have a proof but it uses a difficult lemma.

Definition5

A perfect path double cover (PPDC) for graph 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 vertices is a set of 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 , there exist a path of length at least .

Proof

Consider a PPDC of with paths . , by pigeonhole principle, at least one of the path has length at least .

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 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 edges and the largest set pairwise non-parallel edges has edges, then there exist a path of weight at least .

Posted by Chao Xu on .
Tags: graph theory.