# Critique of my proof of $H(n+1) \leq 2H(n)$

When we speak about graphs, let them be complete. Let the edges be colored red or blue. A $n$-graph is $\textit{Happy}$ if there is a vertex coloring such that each edge touches at least one vertex of its own color. $H(n)$ is the minimum sized graph guaranteed to contain an $n$-happy subgraph and is called the $\textit{Happy Number}$.

$\textbf{Claim: } \; H(n+1) \leq 2H(n)$

Let $Q$ be a $n$-happy subgraph of a $m$-graph such that $H(n) = m$. Consider a graph $G$ of size $2H(n) = 2m$. We wish to show that any graph with $2m$ verticies contains a $(n+1)$-happy subgraph.

Since $|G| \geq m$, $Q$ is a subgraph of $G$. Let $P$ be some vertex in $G$. There are a total of $2m - 1$ blue or red edges which extend from $P$ to the other vertices in $G$. By pigeonhole principle, there must be at least $m$ blue edges or at least $m$ red edges extending from $P$. Partition $G$ into two subgraphs $B$ and $R$ such that all of the vertices in $R$ are connected to $P$ by red edges and all of the vertices in $B$ are connected to $P$ by blue edges. Again, by pigeonhole principle, either $B$ or $R$ will have at least $m$ vertices. Because $H(n) = m$ and $B$ and $R$ partition $G$, then the $m$-graph is contained within $B$ or $R$. Without loss of generality, suppose the $m$-graph is contained within $B$ and let $P$ be blue. Then all of the vertices of $Q$ are connected to $P$ by blue edges. Since $P$ is blue and the edges connected to $Q$ from $P$ are all blue, then $Q$ has a total of $n+1$ vertices and remains happy. Therefore, since there is a $(n+1)$-happy graph contained within $G$, $H(n+1) \leq 2H(n)$.

The basic idea is there, but what you’ve written is a bit confused. For example, you’ve used $Q$ for two different things, an $n$-happy subgraph of $K_m$ and an $(n+1)$-happy subgraph of $G$. Here’s one way to write it up more clearly:
Let $m=H(n)$, let $G=K_{2m}$, and assume that the edges of $G$ have been colored red and blue; we wish to show that $G$ has an $(n+1)$-happy subgraph. Let $v$ be any vertex of $G$. Let $B$ be the set of vertices of $G$ that are connected to $v$ by a blue edge, and let $R$ be the set of vertices of $G$ that are connected to $v$ by a red edge; $\deg_Gv=2m-1$, so one of $B$ and $R$ must contain at least $m$ vertices. Without loss of generality assume that $|B|\ge m$. Let $V$ be any subset of $B$ containing exactly $m$ vertices, and let $G'$ be the subgraph of $G$ induced by $V$; $G'$ is a copy of $K_m$, so it contains an $n$-happy vertex-colored subgraph $Q$. Color $v$ blue, and let $Q'$ be the vertex-colored graph induced by $Q$ and $v$; clearly $Q'$ is $(n+1)$-happy, since the only edges of $Q'$ that aren’t already in $Q$ are the blue edges connected to the blue vertex $v$. Since we started with an arbitrary edge-coloring of $G$, it follows that $H(n+1)\le 2m=2H(n)$.
• I've avoided using the $K_{m}$ notation as it can get confusing later on what we actually mean when a graph is happy. When you say "...so one of $B$ and $R$ must contain at least...", should it be ""$B$ or $R$.." instead? I'm not quite sure what it means for a graph to be induced from another, so you lost me after that. I'll look at this again later. Thank you for your input! – Ozera Oct 14 '15 at 22:46
• @Ozera: ‘One of $B$ and $R$ must contain’ is fine; think of it as short for ‘one (member of the set consisting) of $B$ and $R$ must contain’ if it really bothers you. (In fact I consider it the normal idiom and find ‘one of $B$ or $R$’ very odd indeed.) To say that $G'$ is the subgraph of $G$ induced by $V$ just means that $G'$ consists of the vertices in $V$ and all of the edges of $G$ between any of those vertices. – Brian M. Scott Oct 15 '15 at 6:17