If $G'$ is a subgraph of $G$, and there is a homomorphism to $G\to H$, then exists also $G'\to H$ for every subgraph?

Question

Lets say $G$ has a infinite amount of nodes and $H$ is a finite graph

1. If from every finite subgraph $G'$ from $G$ there is a homomorphism $G'\to H$, then exists also a homomorphism $G\to H$?

2. If there is a homomorphism $G\to H$, then exists also a homomorphism from every finite subgraph $G'\to H$?

3. Is there a formula in Propositional logic, which is only true when homomorphism $N\to M$ exists. Where $N$ and $M$ are two finite graphs?

Answer 1

The first two questions have been handled in the comments, so I'll just give address the third:

You write "Is there formula in propositional logic, which is only true when a homomorphism $N\to M$ exists, where $N$ and $M$ are two finite graphs?" It turns out that even making sense of this question is a bit subtle, so I'll spend some time on that before trying to answer it.

First issue: the answer to the question as stated is trivially "yes". Just take the formula $\top$ (or $P\lor \lnot P$) if there exists a homomorphism $N\to M$, and take the formula $\bot$ (or $P\land \lnot P$) if there is no such homomorphism.

Ok, this is obviously not what the question intends. But how can we make the question more precise to capture the actual intention? Clearly the formula has to depend on the graphs $N$ and $M$, and once you fix the two graphs, there either is a homomorphism, or there isn't...

Second issue: Most propositional formulas are not just flat out true or false. Their truth depends on the truth assignment of their propositional variables. So really the question should ask the formula to be valid (true under any truth assignment) or satisfiable (true under some truth assignment).

Thinking about this suggests a way to resolve both problems, which I suspect is what was originally intended:

Given two finite graphs $N$ and $M$, find a formula in propositional logic such that a truth assignment making the formula true "encodes" a homomorphism $N\to M$, in the sense that there is a natural bijection between the set of satisfying truth assignments and the set of homomorphisms $N\to M$. In particular, the formula is satisfiable if and only if some homomorphism $N\to M$ exists.

Of course, we also want the definition of the formula and the bijection between satisfying truth assignments and homomorphisms to be appropriately uniform in $N$ and $M$. See? I told you it was subtle! Questions like this about reductions between problems, uniformity, etc. are handled elegantly in computability theory and computational complexity theory.

---

Ok, going forward under the interpretation above, I'll give you a outline of an answer.

For each $n\in N$ and $m\in M$, let $P_{n\to m}$ be a propositional variable. A truth assignment to these propositional variables will encode a homomorphism $f\colon N\to M$ by $f(n) = m$ if and only if $P_{n\to m}$ is true. So we need to write down the conditions defining a graph homomorphism as a propositional formula about the variables $P_{n\to m}$.

These conditions are:

• $f$ should be a function. So for each $n\in N$, there should be exactly one $m\in M$ such that $P_{n\to m}$ is true.
• $f$ should respect edges. So for each edge $nEn'$ in $N$, we should have $f(n)Ef(n')$ in $M$. This is probably easier to translate into propositional formula if you rephrase it like this: if $(n,n')$ is pair which is connected by an edge in $N$ and $(m,m')$ is a pair which is not connected by an edge in $M$, then we cannot have $f(n) = m$ and $f(n') = m'$, i.e. $P_{n\to m}$ and $P_{n\to m'}$ cannot both be true.