Can anybody explain me 7x1 case of R(3,4) = 9(K9, complete graph with 9 vertexes)
Ramsey Numbers. Look for table.
What's 7x1...
Suppose the edges of a complete graph on 9 vertices are coloured red and blue. Pick a vertex, v. There are 8 edges incident to v and so (by the pigeonhole principle) at least 4 of them must be the same colour.
Which follows the following cases:
4x4, 5x3, 6x2, 7x1, 8x0.
And in general for any odd solution of R(s,r), how the (n-2)x1 case goes,
In fact, for K5 not to be a solution(but K9 is a solution), for 3x1 case, I gave myself the reason that,
If the 5th vertex of set tries to make an edge with any of the other vertex then that other vertex going to have two edges with that color and hence contradicting the condition. Give that the disjoint subset of 2 vertexes of other 4 vertexes are already connected.
The post is little convoluted, can't find another way to put it.
Thanks.
Edit
First, I wanna mention that i'm developing an intuition as beginner, I did not started with proofs yet.
Okay, le'me rephrase it, let there are 9 vertexes.
Now, Specifically for 7x1 case, there are 4 pairs of vertex are colored with, let's say red color, now if I try to make an edge with the 9th vertex to any of the other 8, it'll cause 2 red colored edge for that vertex which doesn't falls under the case of 7x1, I mean how 7x1 case pass, if we are doing it via Proof by cases.
Is your question just how to show that $R(3,4)=9$? If so you don't need to consider the case in question of $7,1$.
Instead of colouring red and blue and finding complete induced subgraphs, I will just use one colour, and instead find cliques and independent sets.
Clearly we know that $R(3,4) \geq 9$ since for example the cycle $C_8$ with vertices distance $4$ apart adjacent contains no $K_3$ and for each vertex the set of it's non-neighbours induces a $P_4$, which contains no independent set of size $3$ and so the graph cannot contain an independent set of size $4$.
Now let $G$ be a graph on $9$ vertices and let $v$ be a vertex of $G$. As you stated we use the pigeonhole principle and first assume that $v$ has at least $4$ neighbours in $G$, call them $a,b,c,d$. Since $R(2,4)=4$, the graph induced by $a,b,c,d$ either contains an edge (which together with $v$ forms a $K_3$ or an independent set of size $4$.
Next, assume that instead $v$ has at least $6$ non-neighbours. Then using the fact that $R(3,3)=6$, the subgraph induced by these non-neighbours either contains an independent set of size 3 (which along with $v$ forms an independent set of size $4$) or a clique of size 3 (an induced $K_3$).
Now the only case left to check is when $v$ has exactly $3$ neighbours, i.e. the degree of $3$ is exactly $3$. But as $v$ was chosen arbitrarily, all vertices of the graph $G$ have degree $3$, which is a contradiction by the Handshaking lemma as there are an odd number of vertices of odd degree, hence we are done.