Are there any known results showing that existence (or non-existence) of finite graphs with specific computable properties imply certain complexity results (such as P = NP)?
Here's one completely hypothetical result: If a finite graph exists with distingushed edges A, B, C and D such that all maximum matchings either contain all of A, B, C, and D, or contain none of A, B, C and D, then P = NP.
One result of this kind was proved by Lipton "On proving that a graph has no large clique: A connection with Ramsey theory". He connects lower bound conjectures with purely graph theoretic results, showing that if $NP$ is not contained in $coNTIME(n^{O(\log n)})/(\log \log n)$, then the inapproximability of $MAX-CLIQUE$ implies that there are graphs with neat Ramsey-theoretic properties. (See the paper for definitions.) I have no idea if any progress has been made on proving whether or not such graphs actually exist.
Sorry, I came across this 1 year old question only now ...
In fact, there are lots of results showing that explicit graphs with some properties imply strong lower bounds for boolean functions. Say, graphs of high affine or projective dimension imply strong lower bounds for formulas and branching programs. There are also "simpler" measures of graphs, good lower bounds on which would have great consequences in computational complexity. Let me sketch some of them.
View graphs as sets of edges. Let $s(G)$ be the smallest number $s$ such that $G$ can be written as an intersection of $\leq s$ graphs, each of which is a union of $\leq s$ bicliques (bipartite complete graphs). Easy counting shows that $s(G)\geq n^{1/2}$ for almost all bipartite $n\times n$ graphs. But by Valiant's results, every explicit bipartite graph $G$ (more exactly, a sequence of graphs) with $s(G)\geq n^c$ for a constant $c>0$ would resolve an old problem: would give a boolean function which cannot be computed by a log-depth circuit of linear size. It is conjectured that dense graphs without $K_{2,2}$ have large $s(G)$.
Even better, let $Star(G)$ be the smallest number of fanin-$2$ union and intersection operations that are enough to generate $G$ starting with complete stars (graphs of the type $K_{1,n}$ or $K_{n,1}$). Counting shows that most of the graphs have $Star(G)=\Omega(n^2/\log n)$. But any $G$ with $Star(G)\geq (4+c)n$ for a constant $c>0$ would give an explicit boolean function requiring circuits of exponential size! If the graph has dimension $m\times n$ with $m=o(n)$, then even a lower bound $Star(G)\geq (2+c)n$ would have the same consequences. The best we can show so far is $Star(G)\geq 2n-1$.
Let $Sym(G)$ be the smallest number $t$ for which there exists a subset $T\subseteq\{0,1,\ldots,t\}$ and a sequence of $t$ bicliques such that $(u,v)\in G$ iff the number of bicliques containing $(u,v)$ belongs to $T$. Again, counting gives $Sym(G)\geq n/2$ for most of the graphs. But by results of Yao, Beigel and Tarui any explicit graph with $Sym(G)$ larger than $2^{poly(\ln\ln n)}$ would give us a boolean function outside $ACC$. Warning: being "combinatorialy complicated" alone does not imply large $Sym(G)$: there exists strongly Ramsey graphs for which $Sym(G)=O(\log n)$, even if $T$ = set of odd integers.
More details on how all this happens can be found here.
A classical example was by Valiant (I don't know the reference but I think this is described in the book of Hoory, Linial and Wigderson on expander graphs). Valiant showed an explicit lower bound (I think that a certain explicit function $f:{0,1}^n\rightarrow {0,1}^n$ doesn't have a circuit of $O(n)$ size and $O(\log n)$ depth - something we're still far from proving) under the assumptions that certain types of graphs, called superconcentrators, don't exist. (This was an asymptotic question, and not about just one graph.) However he later showed that these do exist (and in fact have other uses)
The answer is certainly "yes" if we talk about families of graphs, rather than specific graphs. For example, there's a conjecture of Mihail and Vazirani that all 0/1 polytopal graphs are either good or very good edge expanders (ie, that their edge expansion is bounded below by 1/polynomial(degree), or 1).
If this is true, then there exist efficient randomized Markov chain Monte Carlo approximation algorithms for a number of open combinatorial and counting problems via a sampling strategy of Alon, Jerrum, and Sinclair.
In a similar vein, if there exist families of polytopal graphs whose diameter grows faster than any polynomial in the number of facets and graph degree, then linear programming cannot be solved in strongly polynomial time via edge-following algorithms.
Expanding on Anand Kulkarni's comment:
Suppose there is a deterministic Turing machine M that recognizes SAT in polynomial time. Then the finite transition relation of M will be a function. We know of TMs that recognize SAT in polynomial time, but their transition relations are not functions. Note that the transition relation is a bipartite directed graph with tuples of (state, tape symbol) in the one bipartition, tuples of (state, tape symbol, move) in the other bipartition, and arcs from pairs to triples.
So trivially if there is such a digraph that is a function, then P=NP.
Of course, this is not a very natural definition, as it requires ancillary machinery to give meaning to the requirement that every path in the state space that reaches the accepting state has length bounded by a polynomial in the input size. It is not at all obvious what the set of finite graphs representing polytime-bounded Turing machines looks like, or whether these graphs have interesting graph-theoretic properties.
