# Graphs with all vertices having more neighbors than 2nd order neighbors

This is the conjecture that inspired my question: https://en.wikipedia.org/wiki/Second_neighborhood_problem

For any vertex $$v$$, let $$N(v)$$ be the set of vertices adjacent to $$v$$ and let $$N^2(v)$$ the set 2nd order neighbors, thus all vertices that have a distance of exactly 2 relative to $$v$$. The conjecture concerns directed graphs, but I was interested in undirected simple graphs with each vertex having strictly more neighbors than second order neighbors. A basic example would be a graph of 4 vertices, completely connected except for one edge.

I believe such graphs are exactly the ones that have the following characteristic: for each vertex $$v$$, more than half of all possible 2-step walks starting from $$v$$ have an endpoint in $$N(v)$$

So far I haven't encountered a counter example but neither can I prove it, it's somewhat intuitive but not completely. Would love to hear your thoughts.

For an extreme counterexample, take $$G = K_{n,n}$$, the complete bipartite graph with $$n$$ vertices on each side. Here, $$|N(v)|=n$$ and $$|N^2(v)| = n-1$$ for all $$v$$, and none of the two-step walks from any vertex $$v$$ end up in $$N(v)$$.
• I think where all the easy-to-find examples are coming from are graphs with a large minimum degree (so $|N(v)| > |N^2(v)|$ because so many vertices are in $N(v)$ we don't have as many left for $|N^2(v)|$). I don't see why there should be a connection to how many $2$-step walks end up in $N(v)$. Commented Jan 24, 2023 at 16:12
• Well you say you want a large minimum degree ( for every vertex thus). But then you will also get large $N^2(v)$ unless you route a part of these paths back to $N(v)$. You're counterexample surpassed this logic completely but I feel like it really was one in a kind in doing that. Commented Jan 24, 2023 at 16:40
• The other way to get small $N^2(v)$ is for the neighbors of vertices in $N(v)$ to have a lot of overlap. (And, yes: if $v$ is adjacent to $w$ and $\deg(w) \ge 2 \deg(v)$, then the neighbors of $w$ not in $N(v)$ are on their own enough to make $N^2(v)$ as large as $N(v)$.) Commented Jan 24, 2023 at 18:55