Let $G$ be a connected (simple) graph with $n$ vertices and at least $n$ edges. Prove that it is possible to color the vertices of $G$ red and blue, so that the following conditions hold: i. There is at least one vertex of each color, ii. There is an even number of edges connecting a red vertex to a blue vertex, and iii. If all such edges are deleted, one is left with two connected graphs.
Problem
Source: 2024 Israel TST Test 6 P1
Tags: combinatorics, TST, graph theory, Coloring
EthanWYX2009
20.03.2024 15:57
I think induction kills it.
PRMOisTheHardestExam
20.03.2024 20:05
pls post how... i can only induct and show if there is vertex of degree 1 then done otherwise cannot think
math90
21.03.2024 03:12
Let me present two solutions. The first proof is direct; the second proof is inductive.
First, we prove a claim.
Claim. It is possible to partition the vertices of $G$ into three nonempty subsets $A_1,A_2,A_3$ such that the following conditions hold:
a) For each $i\in\{1,2,3\}$, the induced graph of $G$ on $A_i$ is connected, and
b) for each $i\in\{1,2,3\}$, there is a direct edge between $A_i$ and $A_{i+1}$, where we denote $A_4=A_1$.
Proof. Let $T$ be a spanning tree of $G$. Since $|E(G)|\ge n$, we can add an arbitrary edge not in $T$ and obtain a connected subgraph $H$ of $G$ with the same set of vertices and exactly $n$ edges. Then $H$ contains a single cycle $C$; let its vertices be $v_1,\ldots,v_m$ where $m\ge 3$. After removing the edges of $C$ from $H$, the resulted graph is a forest with connected components $H_1,\ldots,H_m$ with $v_i\in V(H_i)$. Now choose $A_1=V(H_1)$, $A_2=V(H_2)$ and $A_3=V(G)\setminus (A_1\cup A_2)$. The construction implies that $v_1\in A_1$, $v_2\in A_2$ and $v_3\in A_3$ so $A_1$, $A_2$ and $A_3$ are all nonempty. The fact that $H_1$ and $H_2$ are connected ensure that $A_1$ and $A_2$ are connected. The path $v_3v_4\ldots v_m$ ensures that $A_3$ is connected. Finally, the edges $v_1v_2$, $v_1v_m$ and $v_2v_3$ connect $(A_1,A_2)$, $(A_1,A_3)$ and $(A_2,A_3)$ respectively. $\square$
Now let $A_1$, $A_2$ and $A_3$ be subsets of $G$ satisfying the conditions of the claim. For all distinct $i,j\in\{1,2,3\}$, let $e_{i,j}$ be the number of direct edges between $A_i$ and $A_j$. Among $e_{1,2}$ and $e_{2,3}$ and $e_{3,1}$, two of them have the same parity. WLOG $e_{1,2}$ and $e_{3,1}$ have the same parity. Now color $A_1$ red and $A_2\cup A_3$ blue. Then the number of edges connecting a red vertex to a blue vertex is exactly $e_{1,2}+e_{3,1}$, which is even by assumption.
The assumption that there are at least $n$ edges in $G$ implies that $n\ge 3$. We will prove the problem statement by strong induction on $n$.
Base case: $n=3$. In this case, the graph is a triangle. Then we can color two vertices red and one vertex blue.
Inductive step: suppose $n>3$ and the statement holds for all numbers in $[3,n-1]$. Since there are at least $n$ edges in $G$, then it must contain a nontrivial cycle. Pick a minimal cycle $C$ with vertices $v_1,\ldots,v_m$. We consider two cases:
Case 1. $m=n$. Then $G$ is a Hamiltonian cycle. Coloring one vertex red and the remaining vertices blue works.
Case 2. $m<n$. Then there exists a vertex $v\in V(G)$ not in $C$. Assume that after removing $v$ from $G$, the resulted connected components are $H_1,\ldots,H_p$. WLOG $C$ is a subgraph of $H_1$. We consider two cases.
Case 2.1. $v$ is connected to an even number of vertices in $H_1$. Then coloring $V(H_1)$ red and the remaining vertices blue works.
Case 2.2. $v$ is connected to an odd number of vertices in $H_1$. Since $H_1$ contains a cycle, its number of edges is at least $|V(H_1)|$. Moreover $|V(H_1)|<|V(G)|$ since $v\notin V(H_1)$. Hence we can apply the induction hypothesis on $H_1$ and obtain a coloring of $V(H_1)$ in red and blue, satisfying the problem conditions on $H_1$. Let $r$ and $b$ be the number of vertices in $H_1$ that are connected to $v$ and are red and blue, respectively. Our assumption implies that $r+b$ is odd, so one of $r,b$ is even and the other one is odd. WLOG $r$ is even and $b$ is odd. Let us complete the coloring of $V(G)$ by coloring $V(G)\setminus V(H_1)$ blue. This adds an even number of red-blue edges, so this number remains even. The set of red vertices is connected by construction. Since $b$ is odd, then $b\ge 1$ so $v$ is connected to at least one blue vertex in $V(H_1)$. Hence the set of blue vertices is connected. This finishes the problem.
atdaotlohbh
31.03.2024 23:48
I love this cute problem(actually, all problems from Israel )! In my opinion, two solutions above are quite hard, so I'll post one I found myself(hope it is valid, can someone check it?). We will induct on n. Base case $n=2$ is trivial (no such graph exists, so we are done). Observation 1 If there is a vertex with degree 1, we are done. In this case just delete it, solve the problem for the remaining graph and color the deleted vertex in the original graph the same color as it's neighbour. Observation 2 If we can delete two connected vertices so that graph remains connected, we are done. Call them $A$ and $B$. Because of observation 1, both of them have edges to the remaining graph. If $A$ has an even degree, color it red and all other vertices blue. Same holds for $B$. Now both of them have odd degree, so we can color both of them red and the remaining blue. Observation 3 Such two vertices exist. Consider the spanning tree of our graph. Choose any vertex as a root of the tree. Consider the deepest vertex(or any of them) $A$. It is a leaf, so it is connected only with some vertex $B$. All children of $B$ are also leaves because of maximality. Let's try to delete $A$ and $B$. If it fails, then some children of $B$ are not connected to the remaining graph. But all vertices have degree $\geq 2$, so there is an edge between two children of $B$. Then we can safely delete it, because all children of $B$ are leaves. Done.
math90
01.04.2024 12:16
Above: nice solution. I think in observation 3, you assume the spanning tree is a BFS tree.
topologicalsort
13.10.2024 19:41
Here's a bit different solution, using induction. Base case $n=3$, for which we have that the graph is a triangle, so we can make $2$ of the vertices blue and the other red. Case 1: The graph is a cycle. Then we can choose one of the vertices to be red and the others blue. Case 2: The graph isn't a cycle. We will prove that in this case there is a vertex $v$, such that when we remove it (and its edges) from the graph, the graph remains connected and has $\ge n-1$ edges. Showing that would allow us to use induction. Since the graph isn't a cycle $\exists$ vertex $u$ with $deg(u) \ge 3$. Now construct a spanning tree $T$ which contains all edges that contain $u$. Since $deg(u) \ge 3$, the tree has at least $3$ leaves. This means that if edge $e$ is outside of $T$, then at least one of the leaves is not an endpoint of $e$. We can take the desired vertex $v$ to be one of the leaves not in $e$, because if we remove it, the graph will have a spanning tree and an edge outside of it. Case 2.1: $deg(v)$ is even. Then make $v$ red and the other vertices blue. Case 2.2: $deg(v)$ is odd. Now using induction, take a valid coloring of the graph without $v$. WLOG, since $deg(v)$ is odd, let $v$ be connected to an even number of blue vertices. Now we can make $v$ red which adds an even number to the number of edges with different endpoints, so we are done.