Prove that if $n > 1$ such that $n \to (a,b)$ and $m > n$, then $m \to (a,b)$.

59 Views Asked by At

I've simplified the question's notation to read as follows,

If $n > 1$ such that every graph $H$ on $n$ vertices has $\alpha(H) \ge a$ or $\omega(H) \ge b$ and $m > n$, then every graph $G$ with $m$ vertices has $\alpha(G) \ge a$ or $\omega(G) \ge b.$

My interpretation of this is the idea that if you have a graph on $n$ vertices with a certain clique number and independence numbers, then adding more vertices will never make the clique number or the independence number go down. Is this correct? Does the Ramsey number having to be greater than 1 have anything to do with the proof directly?

What about the other way around? What can I say about removing vertices from a graph with $m$ vertices to form a graph with $n$ vertices?

I need to write a formal proof to show this, but the above is to ensure that I am understanding the problem at hand.

Attempted proof with the above logic:

Proof.
Let $n, m$ be integers.
Suppose that $n > 1$ such that $n \to (a,b)$ and $m > n$.
Let $G$ be a graph with $m > n$ vertices.
For any subgraph $H$ of $G$ with $n$ vertices, $\alpha(H) \ge a$ or $\omega(H) \ge b$, by our assumption.
Since $H$ is a subgraph of G, and $\alpha(H) \ge a$ or $\omega(H) \ge b$, then $\alpha(G) \ge a$ or $\omega(G) \ge b$ will also hold.
So $m \to (a,b)$.

1

There are 1 best solutions below

2
On BEST ANSWER

Prove it the other way around, so you were almost there, and your intuition is right.

Given $G$ with $m > n$ vertices.

Take any subgraph $H$ with $n$ vertices.

The coloring that satisfies the condition for $H$ satisfies the condition for $G$.