query: Knowing every odd circuit in a graph is a triangle, prove $\chi(G) \le 4$
positive_passages.docid: 155090
positive_passages.text: A graph whose every odd cycle is a triangle is 4-colorable
negative_passages.docid: 157939
negative_passages.text: prove that a graph is one-ended
negative_passages.docid: 42367
negative_passages.text: Prove that simple graph $G$ is orientable
negative_passages.docid: 52261
negative_passages.text: Proof that any self-complementary graph has to have $4k$ or $4k+1$ vertex, for some $k \in \mathbb N$
negative_passages.docid: 117992
negative_passages.text: Help with graph induction proof
negative_passages.docid: 48184
negative_passages.text: Prove a graph Containing $2k$ odd vertices contains $k$ distinct trails
negative_passages.docid: 18953
negative_passages.text: Prove that even + odd is odd.
negative_passages.docid: 100168
negative_passages.text: Prove the existence of a graph of 15 vertices with some vertices degree given
negative_passages.docid: 4112
negative_passages.text: How to prove that a simple graph having 11 or more vertices or its complement is not planar?
negative_passages.docid: 59831
negative_passages.text: How to relate combinatorial proof to bipartite graphs?
negative_passages.docid: 71990
negative_passages.text: Prove there always exists a partition such that vertices in each part have even degree
negative_passages.docid: 140444
negative_passages.text: Prove $\chi(G)\chi(\bar{G}) \geq n$ for chromatic number of graph and its complement
negative_passages.docid: 79040
negative_passages.text: Graph of $|x| + |y| = 1$
negative_passages.docid: 133270
negative_passages.text: Prove that the chromatic polynomial of a cycle graph $C_{n}$ equals $(k-1)^{n} + (k-1)(-1)^{n}$
negative_passages.docid: 99781
negative_passages.text: Proof that any simple connected graph has at least 2 non-cut vertices.
negative_passages.docid: 105910
negative_passages.text: How to prove that $[G:xHx^{-1}] = [G:H]$ given $H \le G$?
negative_passages.docid: 90747
negative_passages.text: Upper bound on $\chi(G)$ for a triangle-free graph