Vertex-Based Localization of Erdős-Gallai Theorems for Paths and Cycles

For a simple graph $G$, let $n$ and $m$ denote the number of vertices and edges in $G$, respectively. The Erdős-Gallai theorem for paths states that in a simple $P_k$-free graph, $m\le \frac{n(k-1)}{2}$, where $P_k$ denotes a path with length $k$ (that is, with $k$ edges). In this paper, we generalize this result as follows: For each $v\in V(G)$, let $p(v)$ be the length of the longest path that contains $v$. We show that $$m\le \sum _{v\in V(G)}\frac{p(v)}{2}$$ The Erdős-Gallai theorem for cycles states that in a simple graph $G$ with circumference (that is, the length of the longest cycle) at most $k$, we have $m\le \frac{k(n-1)}{2}$. We strengthen this result as follows: For each $v\in V(G)$, let $c(v)$ be the length of the longest cycle that contains $v$, or $2$ if $v$ is not part of any cycle. We prove that $$m\le \left(\sum _{v\in V(G)}\frac{c(v)}{2}\right)-\frac{c(u)}{2}$$ where $c(u)$ denotes the circumference of $G$. \newline Furthermore, we characterize the class of extremal graphs that attain equality in these bounds.