1
$\begingroup$

The following is an exercise from an introductory course on combinatorics.

Let $G$ be a finite simple graph, and color its edges such that every color appears exactly twice. Assume that from every vertex there are at least $4$ different colors. Prove that it is possible to remove some edges such that there will not be any duplicate colors remaining, and yet every vertex will still have at least one neighbor.

In other words, we are looking for a spanning subgraph without isolated vertices and with distinct colors.

I tried to remove edges in an explicit algorithm and avoiding the removal of edges that will make the process stuck, but the order of removal seems to be too dependent on the topology of the specific graph at hand. I also tried to remove edges independently with some probability $p$, but there seem not to be any $p$ that works for both conditions. As a sidenote, I believe that the course from which this exercise is taken does not assume knowledge of the probabilistic method.

$\endgroup$
1
$\begingroup$

It's possible to choose which edges to keep by applying Hall's theorem.

Define an auxiliary bipartite graph as follows:

  • On side $A$, the vertices are the vertices of $G$.
  • On side $B$, the vertices are the colors appearing in the edge-coloring of $G$.
  • There is an edge from vertex $a$ to color $b$ if color $b$ appears on one of the edges out of $a$.

Then an $A$-perfect matching in this graph corresponds to a choice of one color for each vertex of $G$ such that no color is chosen twice. This tells us which edges to keep: if edge $(a,b)$ is in the matching, keep the edge out of vertex $a$ which has color $b$. This guarantees no vertex is left isolated, because each vertex has at least one edge out of it that we keep. Additionally, no color is used more than once, because no color appears in more than one edge of the matching.


To check Hall's condition, let $\{a_1, a_2, \dots, a_k\}$ be any set of vertices. Counted with multiplicity, there are $4k$ colors appearing on the edges out of those vertices in $G$. Each color can appear at most $4$ times: a color is used on only two edges out of $G$, which have $4$ endpoints. So among the $4k$ colors, there must be at least $k$ distinct colors. Therefore Hall's condition is satisfied: in the auxiliary bipartite graph, $N(\{a_1,a_2, \dots,a_k\})$ has size at least $k$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.