# Generalize the relationship between path length and minimum degree to weighted graphs

Let $\delta(G)$ be the minimum degree of a simple graph $G$. A well known theorem states that every simple graph $G$ contains a path of length $\delta(G)$.

Can this be generalized to weighted graphs? Consider a weighted graph $G=(V,E,w)$, $w$ is a weight function $w: E\to \mathbb{R^{\geq 0}}$.

Let the weighted degree of a vertex be $d:V\to \mathbb{R^{\geq 0}}$, where $d(v) = \sum_{v\in e\in E} w(e)$.

The minimum weighted degree is therefore $\delta(G) = \min_{v\in V} \{d(v)\}$.

The weight of a path equals the sum of edge weights on the path.

Conjecture: Every weighted simple graph $G$ contains a path of weight at least $\delta(G)$.

There is a theorem for connected graph. If $G$ is a simple connected graph then it contains a path of length $\min \{2\delta(G),|G|-1\}$, what would be the analogue of that?

-

Consider the longest path $v_1,\ldots,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,\ldots,v_{i-1},v_i,v_n,v_{n-1}\ldots,v_{i+1}$ would be longer, a contradiction. Therefore we have

$$\delta(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}\})$$

Thus it proves the result.

Similarly, we can also get

$$\delta(G) \leq \sum_{\{v_1,v_i\}\in E} w(\{v_1,v_i\}) \leq \sum_{i=2}^n w(\{v_{i},v_{i-1}\})$$

We can see that we could even get a path of length $2\delta(G)$ if there is no $i$, such that both $\{v_1,v_{i+1}\}$ and $\{v_i,v_n\}$ is an edge.

-