1
$\begingroup$

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)$.

$\endgroup$
1
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Ozera Oct 14 '15 at 22:46
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Oct 15 '15 at 6:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.