The Art Gallery Guardian

There exist a path of length d(G)\lceil d(G)\rceil for every graph GG


1 Unweighted Graph

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

Lemma1

If GG is a connected graph, then it contain a path of length min(2δ(G),G1)\min(2\delta(G), |G|-1), where δ(G)\delta(G) is the minimum degree of GG.

The above lemma is Exercise 1.7. in Graph Theory by Diestel. ::: {.Lemma #lem:densecomp} Every graph GG has a component HH, such that d(H)d(G)d(H)\geq d(G). ::: ::: Proof Fact: If xi,yi>0x_i,y_i>0 and xiyi<t\frac{x_i}{y_i} < t for all 1ik1\leq i\leq k, then i=1kxii=1kyi<t\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 H1,,HkH_1,\ldots,H_k, d(Hi)=2e(Hi)Hi<d(G)d(H_i) = \frac{2e(H_i)}{|H_i|} < d(G), then d(G)=i=1k2e(Hi)i=1kHi<d(G)d(G) = \frac{\sum_{i=1}^k 2e(H_i)}{\sum_{i=1}^k |H_i|} < d(G), a contradiction. ::: ::: Theorem A simple graph GG must contain a path of length at least d(G)d(G). ::: ::: Proof Proof by induction. It is true for graph with 1 vertex. Assume it is true for all graphs with kk vertices, k<nk < n. Consider graph GG of nn vertices. If the graph has more than 1 component, then we use [???] and show there exist a subgraph HH with strictly smaller number of vertices, such that d(H)d(G)d(H)\geq d(G), and just apply the induction hypothesis.

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

2 Weighted Graph

Can we generalize this problem to weighted graphs? G=(V,E)G=(V,E), (G,w)(G,w) is a weighted graph, where w:ERw: E\to \mathbb{R}. Define the average weighted degree of graph GG to be dw(G)=2eEw(e)G, d_w(G) = \frac{2\sum_{e\in E} w(e)}{|G|}, and the minimum weighted degree δw(G)=mineE{w(e)}. \delta_w(G) = \min_{e\in E} \{w(e)\}. If PP is a path, then the weight of the path is W(P)=ePw(e)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)\delta_w(G).

Theorem2

For a weighted graph (G,w)(G,w), there exist a path of weight at least δw(G)\delta_w(G).

Proof

Consider the longest path v1,,vnv_1,\ldots,v_n. Claim: w({vi,vn})w({vi,vi+1})w(\{v_i,v_n\})\leq w(\{v_i,v_{i+1}\}) for all ii. Assume not, then the path v1,,vi1,vi,vn,vn1,vi+1v_1,\ldots,v_{i-1},v_i,v_n,v_{n-1}\ldots,v_{i+1} would be heavier, a contradiction. Therefore we have δw(G){vi,vn}Ew({vi,vn})i=1n1w({vi,vi+1})=W(v1vn) \delta_w(G) \leq \sum_{\{v_i,v_n\}\in E} w(\{v_i,v_n\}) \leq \sum_{i=1}^{n-1} w(\{v_i,v_{i+1}\}) = W(v_1\ldots v_{n})

However, we want something stronger, say instead of δw(G)\delta_w(G), can it be dw(G)d_w(G)? I have a proof but it uses a difficult lemma.

Definition3

A perfect path double cover (PPDC) for graph GG 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 nn vertices is a set of nn paths.

Lemma4

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.

Theorem5

For a weighted graph (G,w)(G,w), there exist a path of length at least dw(G)d_w(G).

Proof

Consider a PPDC of GG with nn paths p1,,pnp_1,\ldots,p_n. i=1nl(pi)=ndw(G)\sum_{i=1}^n l(p_i) = nd_w(G), by pigeonhole principle, at least one of the path has length at least dw(G)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))O(m\Delta(G)) time, so we actually have a polynomial time algorithm for this.

This give us a fun problem.

Problem6

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

Posted by Chao Xu on .
Tags: graph theory.