$ G=(V,E_1 \cup E_2) $ is a triangle free graph, where $ G_1=(V,E_1) $ is planar and $ G_2 = (V, E_2)$ is a tree. Prove that: $ \chi (G) < 7 $

94 Views Asked by At

can anyone help with this, any direction could be helpfull? I've tried using the fact that $ G_1 $ satisfies that it's planar and is triangle free because G is. So we should have $|E_1| \leq 2|V|-4 $ and for the tree we have $|E_2| = |V|-1 $.

So in G we have $|E| \leq 3|V|-5 $ from this we know that $2|E| \leq 6|V|-10 $ $ \Rightarrow \exists v \in V : d(v)<6 $ Now I'm thiking about induction but I really am stuck

1

There are 1 best solutions below

1
On

Since you want a non-inductive argument, I shall provide one. The statement to be proven is as follows:

Let $G(V,E)$ be a triangle-free graph on the vertex set $V$ with the edge set $E$. Suppose that $E$ can be partitioned into two sets $E_1$ and $E_2$ such that the edge-induced subgraph $G\left[E_1\right]$ is planar, while $G\left[E_2\right]$ is a forest. Then, $\chi(G)<7$.

We shall prove by contradiction. Suppose contrary that there exists such a graph $G$ with $\chi(G)\geq 7$. Clearly, $G$ has at least $1$ vertex. Choose one with the smallest number of vertices. Therefore, using the same argument as suggested by the OP (now with $\left|E_2\right| \leq |V|-1$ instead of equality), there exists a vertex $v$ of $G$ with $\deg_G(v)\leq 5$. Define $G'$ to be the vertex-induced subgraph $G\big[V\setminus\{v\}\big]$ of $G$. Since $G'$ has a smaller number of vertices and $G'$ also satisfies the same condition, we must have $\chi\left(G'\right)<7$. Pick a coloring of vertices of $G'$ by at most $6$ colors. Since $v$ is adjacent to at most $5$ vertices of $G'$, there exists a color not shown among the neighbors of $v$. Extend this vertex coloring on $G'$ to a vertex coloring on $G$ by coloring $v$ with one of the colors not used among the neighbors of $v$. Hence, $G$ has a vertex-coloring by at most $6$ colors, contradicting the assumption that $\chi(G)\geq 7$. That is, such a graph $G$ cannot exist.

P.S.: To be fair, this is induction in disguise.