Connected, not n-colourable graph

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Connected, not n-colourable graph

G H J

Reveal topic tags

combinatorics proposed

L

G H BBookmark kLocked kLocked NReply

Source: Tuymaada 2013, Day 1, Problem 4 Juniors and 3 Seniors

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

15142 posts

#1 h Jul 20, 2013, 9:22 PM • 7 Y

Y by Amir Hossein, Smoothy, Vietjung, Adventure10, Mango247, and 2 other users

The vertices of a connected graph cannot be coloured with less than $n+1$ colours (so that adjacent vertices have different colours).
Prove that $\dfrac{n(n-1)}{2}$ edges can be removed from the graph so that it remains connected.

V. Dolnikov

EDIT. It is confirmed by the official solution that the graph is tacitly assumed to be finite.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

15142 posts

#2 h Jul 20, 2013, 9:52 PM • 6 Y

Y by fermat007, Amir Hossein, Vietjung, Adventure10, Mango247, and 1 other user

In other words, we are asked to show we can remove (at least) $\dfrac{n(n-1)}{2}$ edges of a connected graph $G = (V,E)$ , with chromatic number $\chi(G) > n$ , so that $G$ remains connected. Although, most likely, the problem refers to finite graphs, the de Bruijn - Erdös theorem allows the consideration of infinite graphs as well.

Theorem.An infinite graph $G$ can be coloured with $k$ colours (so that adjacent vertices bear different colour) if and only if any finite subgraph of it can be thus coloured with $k$ colours.

As a consequence, if $G$ is infinite, with $\chi(G) > n$ , then there exists a finite subgraph $H$ of it, with $\chi(H) > n$ (the issue of the connectedness of $H$ is moot, since we may consider its connected component of maximal chromatic number, which must be larger than $n$ ). We then remove $\dfrac{n(n-1)}{2}$ edges from $H$ , and since $G$ was connected, putting back the vertices from $G - H$ keeps the graph connected. In the sequel we will therefore assume $G$ is finite.

Let $m$ be the number of edges of a finite graph $G$ ; then
$\chi(G) \leq \dfrac {1} {2} + \sqrt{2m +\dfrac {1} {4}}.$
Proof. Let be a colouring of $G$ with $k=\chi(G)$ colours. Then $G$ has at least one edge connecting any two colour classes; otherwise we could use a same colour for both classes. Therefore $m\geq \dfrac {k(k-1)} {2}$ , the very conclusion we desired. Another (trivial) result is $\chi(G) \leq \Delta(G) + 1$ , where $\Delta(G)$ is the largest degree of a vertex of $G$ .
In our case we therefore have $m \geq \dfrac {n(n+1)} {2} = \dfrac {n(n-1)} {2} + n$ , and at least we now know a graph with $\chi(G)\geq n+1$ has enough edges so we can remove $\dfrac{n(n-1)}{2}$ of them. On the other hand, we also have $\Delta(G) \geq n$ .

Let us notice that $\dfrac{n(n-1)}{2}$ is the largest value generally possible; for $G=K_{n+1}$ (the complete graph on $n+1$ vertices $v_1,v_2,\ldots,v_n,v_{n+1}$ ) we can remove $\displaystyle \binom {n+1} {2} - n = \dfrac{n(n-1)}{2}$ edges (being left with the (connected) Hamiltonian path $v_1v_2\ldots v_nv_{n+1}$ with $n$ edges), but not more.

The solution goes by induction on $|G| + n$ . Initial cases are trivial, so we pass right to the induction step. It is easy to see there exists a vertex $v$ which does not disconnect the graph when removed. Let $G - v$ .
If $\chi(G - v) > n$ , then by the induction hypothesis we may remove from $G - v$ a set $M$ of edges, having $|M| \geq \dfrac{n(n-1)}{2}$ , so that the graph remains connected, but then the graph $G' = (V, E\setminus M)$ will also be connected.
Otherwise, since $\chi(G - v) \geq \chi(G) - 1 > n-1$ (in fact then $\chi(G - v) = n$ ), we may remove from $G - v$ a set $M$ of edges, having $|M| \geq \dfrac{(n-1)(n-2)}{2}$ . But clearly $\deg v \geq n$ , so we may remove at least $n-1$ edges incident at $v$ from $G' = (V, E\setminus M)$ , which therefore remains connected after the removal of (at least) $\dfrac{(n-1)(n-2)}{2} + (n-1) = \dfrac{n(n-1)}{2}$ edges.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5850 posts

#3 h Jul 21, 2013, 4:27 AM • 12 Y

Y by Amir Hossein, Nguyenhuyhoang, TheStrangeCharm, GGPiku, Kayak, lifeisgood03, Vietjung, mijail, Adventure10, math_comb01, and 2 other users

Another solution: we color the graph by going through each vertex individually. Pick an arbitrary vertex and give it color number $1$ . Then at each step, choose another vertex adjacent to at least one vertex we've colored already, and give it the smallest number color that is valid. Furthermore, each time we give a vertex $v$ a color $k$ , we know it is adjacent to colors $1, 2, \ldots, k-1$ . If $k \geq 3$ , erase the edges connecting $v$ to vertices of color greater than $1$ ; the graph is still connected.

At the end, we've used all of the colors $1, 2, 3, \ldots, n+1$ at least once, so we've erased at least $1 + 2 + 3 + \cdots + (n-1)= \dfrac {n(n-1)} {2}$ edges. The final graph is still connected, so we're done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

15142 posts

#4 h Jul 21, 2013, 10:06 AM • 6 Y

Y by Amir Hossein, Vietjung, Adventure10, Mango247, and 2 other users

The above is based in essence on the following

Proposition 1.4.1. [Reinhard Diestel - Graph Theory] The vertices of a connected (finite) graph $G$ can always be enumerated, say as $v_1,\ldots,v_{|G|}$ , so that $G_i := G[v_1,\ldots,v_i]$ is connected for every $i$ .

Now the coloring is done running through the enumeration provided by this proposition, via the greedy algorithm, and the removal of edges is done as stated above. Quite short and sweet.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1298 posts

Kayak

#5 h Jun 19, 2018, 9:47 AM • 2 Y

Y by Adventure10, Mango247

This is most probably a silly question, but

mavropnevma wrote:

In our case we therefore have $m \geq \dfrac {n(n+1)} {2} = \dfrac {n(n-1)} {2} + n$ , and at least we now know a graph with $\chi(G)\geq n+1$ has enough edges so we can remove $\dfrac{n(n-1)}{2}$ of them . On the other hand, we also have $\Delta(G) \geq n$ .

I understand how the bound of $|E| \geq \binom{\chi(G)}{2} = \binom{\chi(G)-1}{2} + \chi(G)-1$ is proved, and I also know that how the bound of $\Delta(G) \geq \chi(G) - 1$ is proved, but I don't see how putting them together leads the conclusion of the problem. Can somebody explain how it's relevant to the problem or how mavropnevma reaches to the conclusion in the bolded part ?

I think using these two bounds, you can prove the weaker version that $|E| - \Delta(G) \geq \binom{\chi(G)-1}{2}$ but we need to prove the stronger version $|E|-|V|+1 \geq \binom{\chi(G)-1}{2}$ for the problem, right ?

This post has been edited 2 times. Last edited by Kayak, Jun 19, 2018, 9:49 AM
Reason: Added second part

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

615 posts

#6 h Jun 20, 2018, 8:30 AM • 3 Y

Y by Kayak, Adventure10, Mango247

The two bounds are not really relevant to the solution --- I guess they are just some of marvropnevma's initial thoughts. My understanding of the bolded part doesn't refer to being able to remove $\frac{n(n-1)}{2}$ edges from $G$ so that it remains connected but rather at the very least there is enough edges for it to be possible that $G$ is connected after removing that many edges (since a connected graph needs at least $n-1$ edges).

If you read through his solution, there is a part where he claims "But clearly $\deg v \geq n$ ." This doesn't directly follow from $\Delta(G) \geq n$ but the proof is similar so that might be why he mentioned it.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

492 posts

#7 h Jul 7, 2020, 4:04 AM

Y by

redacted

This post has been edited 2 times. Last edited by fukano_2, Oct 27, 2021, 10:37 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

13 posts

#8 h May 31, 2025, 10:42 PM

Y by

We call a vertex coloring of a graph proper if there are no edges between any two vertices of the same color.

Lemma 1:
If the degree of every vertex is at most $n$ , then the vertices can be properly colored using $n+1$ colors.

Proof:
Let the set of available colors be $[1, 2, \dots, n+1]$ .
We color the vertices one by one. For each vertex, we assign it the smallest color that has not been used by any of its neighbors.
Since each vertex has at most $n$ neighbors, there is always at least one unused color among the $n+1$ , so this greedy coloring procedure succeeds.
Hence, a proper coloring with $n+1$ colors exists.

⸻

Lemma 2:
If a graph cannot be properly colored with $n$ colors, then it contains a connected subgraph in which the degree of every vertex is at least $n$ .

Proof:
We proceed by contradiction. Suppose the graph contains no such subgraph.
Then, repeatedly remove any vertex with degree less than $n$ .
If the removal of a vertex causes another vertex’s degree to drop below $n$ , we remove that one too.
Since no subgraph with all degrees $\geq n$ exists, this process eventually removes all the vertices.

Now reverse the process: add back the vertices one by one in reverse order of deletion.
At each step, the degree of the newly added vertex (in the current graph) is less than $n$ .
By Lemma 1, we can assign it a color using at most $n$ colors, maintaining a proper coloring throughout the reconstruction.
Therefore, the entire graph can be properly colored with $n$ colors — a contradiction.

Hence, such a connected subgraph must exist
.
—————

Now we proceed to the solution.
By Lemma 2, the graph contains a connected subgraph in which every vertex has degree at least $n$ .
We now prove that we can remove $\dfrac{n(n-1)}{2}$ edges from this subgraph and it remains connected.

Let this subgraph contain $N$ vertices. Clearly, $N \geq n + 1$ .
Then the number of edges satisfies:

$E - \frac{n(n-1)}{2} = \frac{\sum d(v_j)}{2} - \frac{n(n-1)}{2} \geq \frac{Nn}{2} - \frac{n(n-1)}{2}$

We want to prove that:

$\frac{Nn}{2} - \frac{n(n-1)}{2} \geq N - 1$

This would imply that even after removing $\frac{n(n-1)}{2}$ edges, at least $N - 1$ edges remain — the minimum needed to keep a graph with $N$ vertices connected (i.e. form a spanning tree).

We prove the inequality:

$\frac{Nn}{2} - \frac{n(n-1)}{2} \geq N - 1$

Multiply both sides by 2:

$Nn - n^2 + n \geq 2N - 2$

Bring all terms to one side:

$Nn - 2N - n^2 + n + 2 \geq 0$

Group terms:

$N(n - 2) - n^2 + n + 2 \geq 0$

Now plug in $N = n + 1$ (since $N \geq n + 1$ ):

$(n+1)(n - 2) - n^2 + n + 2 = 0$

Thus the inequality holds.
So after removing $\frac{n(n-1)}{2}$ edges, the subgraph still contains at least $N - 1$ edges and remains connected.

This post has been edited 1 time. Last edited by OutKast, May 31, 2025, 10:45 PM
Reason: Forget the latex

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a