Closed Walks and Edge Addition If $G$ is a simple graph with adjacency matrix $A$, then $c_k(G):=\mbox{tr}A^k$ gives the number of closed walks in $G$ of length $k$. Let $G'$ denote the graph obtained from $G$ by adding an edge between any two vertices (no multiple edges allowed). Then one should have $c_k(G)\leq c_k(G')$. My question is the following. Is it true that $c_k(H)\leq c_k(G)$ implies $c_k(H')\leq c_k(G')$ ? It feels like it should be true but cannot seem to prove this fact. Any references would be appreciated.
Edit: Graphs $G$ and $H$ have the same order and are connected.
 A: This does not hold in general. Let's set $k=3$ and consider the following counterexample:

Here, $c_3(H) = 6$ (there are $3$ closed walks per triangle), which is strictly less than $c_3(G) = 9$.
The only possible edge we can add to $H$ is the one showed with a dashed line (this way $H$ turns into a $K_4$). And there are several edges that we can add to $G$, but all of them accomplish the same: Connect one vertex of one triangle to another.
Then $c_3(H') = 12$, because there will be $3$ small triangles and $1$ large one, a total of $4$ triangles, and there are still $3$ closed walks per triangle subgraph. But $c_3(G')$ doesn't change, there are no new closed walks of length $3$.
So $c_3(H) < c_3(G)$, but $c_3(H') > c_3(G')$.
A: I think that your conjecture is false.
For example, let $H$ be a cycle of length $6$ and $G$ a cycle of length $7$.  And let $H', G'$ be $H,G$ with the addition of one edge (say, for example, $(1,3)$)
Unless I've made a mistake this is a counterexample to the conjecture: $c_7(H) = 0$ and $c_7(G) = 14$, but $c_7(G') = 350$ and $c_7(H') = 434$.  So the order flips after the addition of an edge.
My guess is that for "most" graphs and "most" lengths your conjecture holds, though.
A: I have given an answer yesterday, but the question was since augmented with two other requirements.
If we require $G$ and $H$ to be of the same order and to both be connected, then there is still a counterexample:

Here, $|V(G)| = |V(H)| = 6$, and let us consider the case of $k=3$ again.
It is generally true that
$$\# \{ \text{walks of length } 3 \} = 3 \cdot \# \{ \text{triangles of length }3\}$$
(Or if we consider walks in the opposite direction different, then it's $6 \cdot \# \{ \text{triangles of length } 3\}$; however, this won't change the result, as it will simply multiply every value by a factor of $2$.)
Then

*

*$c_3(H) = 12$, because there are $4$ triangles in it.

*$c_3(G) = 15$, because the $K_4$ contains $4$ triangles, and one extra was appended to it, making it contain $5$ triangles in total.

*$c_3(H') = 24$, because the $4$ triangles remain, but we actually created $4$ new triangles with the new edge, so it contains a total of $8$ triangles.

*$c_3(G') = 18$, because the $5$ triangles remain, and we only created one new one, since the new edge connects to a vertex that had a degree of $1$, so no other triangles get created; making it have a total of $6$ triangles.

So even though $H, G, H'$, and $G'$ are all connected graphs with $|V(H)| = |V(G)|$ and $|V(H')| = |V(G')|$, we were still able to find a counterexample where

*

*$c_3(H) < c_3(G)$, but

*$c_3(H') > c_3(G')$.

