4
$\begingroup$

Prove that every $k$-chromatic graph has size $m\geq \binom k2$.

Here is what I know:

Let $G$ be a $k$-chromatic graph, that mean $\chi(G)=k$. Thus $G$ must have a subgraph of a complete $k$-partite graph, say $H$. Hence $m_G \geq m_H$.

Here are my questions

1) I'm kinda confused between $k$-coloring, $k$-colorable and $k$-chromatic.

I know that $G$ is $k$-colorable means $\chi (G) \leq k$ and $\chi(G)$ is the minimum number of colors needed for a legal coloring of $G$. Then the book said if $G$ is $k$-chromatic then there exists a $k$-coloring but no $(k-1)$-coloring.
I feel like the book is just kicking me around.

2) I know $\binom k2$ is the size of a complete graph of order $k$, but I can't see how a $k$-partite graph has that size.

$\endgroup$
1
  • 1
    $\begingroup$ I have changed the formatting of the title so as to make it take up less vertical space -- this is a policy to ensure that the scarce space on the main page is distributed evenly over the questions. See here for more information. Please take this into consideration for future questions. Thanks in advance. Also note that binomial coefficients have an own command (both in TeX and MathJax): \binom{n}{k} $\binom nk$ $$\binom nk$$ $\endgroup$
    – AlexR
    Feb 5, 2015 at 23:53

5 Answers 5

9
$\begingroup$

Let G be a $k$ chromatic graph of order $n$ and size $m$. Let there be given a coloring of $G$ using $k$ colors. Denote the color classes of G by $C_1,C_2,...C_k$. We're gonna run the ol' proof by contradiction here. I'm not sure if it's necessary, but whatever, I like it. So, we assume that $m<\binom{k}{2}$ Now, doesn't this already seem weird? $G$ has less edges than $K_k$? We get our contradiction from this last curiosity. Consider the graph $H$, formed by associating each color class, $C_i$, with a vertex, $u_i$ where$\; 1\le i\le k$ and $u_iu_j\in E(H), i\ne j, $ if and only if $\exists$ an edge between any vertex in $C_i$ and any vertex in $C_j$. Since $|E(G)|=m<\binom{k}{2}$ and since $H$ necessarily has less edges than $G$, it follows that $H$ is not a complete graph. Therefore, there exists 2 color classes, $C_m$ and $C_n$ $(m\ne n),$ with no edge between them. Change the color of all vertices in $C_m$ to the color of the vertices in $C_n$. This produces a coloring of $G$ with $k-1$ colors, a contradiction. Therefore, it must be the case that $m\ge \binom{k}{2}$

$\endgroup$
5
  • $\begingroup$ Anyone got any questions? $\endgroup$ Feb 6, 2015 at 0:39
  • $\begingroup$ I only have one question, at the point you said $G$ have less edges than $K_k$, can I stop right there? Because if $G$ has less edge than $K_k$ then there exist less than $k-coloring$ in $G$ already, right? And this contradict the definition of $k-chromatic$ directly? $\endgroup$ Feb 6, 2015 at 0:42
  • 1
    $\begingroup$ By the way, you did a great job on explaining this problem. I would gave you more than one vote if I could. $\endgroup$ Feb 6, 2015 at 0:45
  • $\begingroup$ Thank you ;). I'm not so sure you can stop at that point. That would essentially be assuming the theorem true before you do so yourself. I think the details need to be fleshed out. $\endgroup$ Feb 6, 2015 at 0:49
  • $\begingroup$ I see, it makes a lot more sense when you got every thing justified. Thank you again. $\endgroup$ Feb 6, 2015 at 0:52
8
$\begingroup$

Suppose $G$ is $k$-chromatic. Consider a proper coloring of $G$ with $k$ colors; call the colors $1,\dots,k$. For each pair of colors $i,j$ ($1\le i\lt j\le k$) there must be at least one edge joining a vertex of color $i$ to a vertex of color $j$; for, if there were no such edge, then we could collapse colors $i$ and $j$ to a single color, and get a proper coloring of $G$ with only $k-1$ colors. Since there is at least one edge for each pair of distinct colors, the graph $G$ has at least $\binom k2$ edges.

$\endgroup$
5
$\begingroup$

I think you can also argue like this. $G$ is $k$-chromatic, so $G$ has a subgraph of complete $k$-partite. Since every vertices in the same partite has the same color, you can treat each partite as one vertex. This is a complete $k$-partite so every partite is connected to $k-1$ other partites. If you treat each partite as a vertex, then you will have $K_k$ which has exactly $\binom{k}{2}$ edges. Since every partite has at least 1 vertices so the number of edges in the $k$-partite is at least $\binom {k}{2}$ edges, thus $m_G \geq \binom{k}{2}$

$\endgroup$
1
  • 2
    $\begingroup$ While this question is temporarily active, let me remark that this is false: a $k$-chromatic graph does not necessarily have a complete $k$-partite subgraph. In particular, when $k\ge 3$, any $k$-partite subgraph contains a cycle of length $3$, but the $5$-cycle is a $3$-chromatic graph with no such cycle. the iterated Mycielskians provide a more general family of counterexamples. Also, "partite" is not a noun. $\endgroup$ May 8, 2019 at 23:48
0
$\begingroup$

This question was also answered here:

Prove, that graph $G$ has at least $\chi(G)(\chi(G)-1)/2$ edges.

since $\binom{k}{2} = k(k-1)/2$

$\endgroup$
2
  • 1
    $\begingroup$ One of these questions should probably be marked as a duplicate of the other. Unclear which one. This question has more answers, but the other question has fewer wrong answers... $\endgroup$ May 8, 2019 at 23:50
  • $\begingroup$ The question in this link was asked first (2014) and has a nice pithy answer with more upvotes, so perhaps the question here (2015, by Diane Vanderwaif) should be marked as the duplicate. (If I had the reputation I'd do it myself.) That said Diane's question has generated a lot more useful discussion so it's worth keeping around. $\endgroup$ May 9, 2019 at 0:20
-1
$\begingroup$

Basically for a $k$ chromatic graph with $n$ vertices, there are $k$ edges such that all are adjacent to each other which mean every 2 vertices of those $k$ vertices are connected, i.e, there are at least $_kC_2$ (or $\binom k2$) edges in the graph.

$\endgroup$
1
  • 1
    $\begingroup$ This is another wrong answer to this question (and $C_5$ is still a counterexample) $\endgroup$ May 8, 2019 at 23:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .