Let $G$ be a simple graph such that for every $k$ pairwise distinct edges in $G$ at least two of those edges have the same endpoint.

coloringgraph theory

Question

Let $k$ be a positive integer such that $k \geq 2$. Let $G$ be a simple graph such that for every $k$ pairwise distinct edges in $G$ at least two of those edges have the same endpoint. Show that the chromatic number of $G$ is at most $2k-1$.

Attempt/Thoughts

My thought is to simply consider $k=|E|$, the number of edges in the graph $G$ (I believe they are all pair-wise distinct, not sure why the question has to elaborate on this point..)

Then at least two of those edges have the same endpoint. Not sure how to proceed.

Another approach would be to assume by contradiction that the chromatic number $\gamma > 2k-1$, but I'm not sure how to argue this point.

Any hints much appreciated.

Best Answer

Let us assume that $k$ is minimal. Next for any subset $A$ of edges of $G$, let us write as $V_A$ the set of vertices covered by $A$. So as $k$ is minimal, a maximum matching $M^*$ of $G$ has precisely $k-1$ edges [why is this]. So letting $M^*$ be an arbitrary maximum matching, let $A=M^* + \{e\}$, for any edge $e$ in $E(G)\setminus M^*$, with at least one endpoint outside of $V_{M^*}$. [There exists such an edge $e$, lest $G$ is a graph with only $2k-2$ vertices having positive degree and the rest having degree 0, in that case it would be easy to color $G$ with $2k-2$ colors.] Then $A$ is a subset of precisely $k$ edges, and as $A$ cannot be a matching itself [because $k-1$ is the size of the largest matching in $G$] it follows that $e$ has exactly one endpoint outside of $V_{M^*}$. So $A$ is 'almost' a matching as well ; one component of $A$ is a path w 3 vertices and the remaining components of $A$ have 2 vertices each, and $|V_A|$ is precisely $2k-1$.

Claim 1: Let $w$ be a vertex in $V\setminus V_A$. Then $w$ is not adjacent to every vertex in $V_A$.

Otherwise if $w$ were adjacent to every vertex in $V_A$ then there would be a matching $M$ that covers $V_A +\{w\}$ [which $2k$ vertices] and so $|M|$ would be $k$.

Claim 2: Let $w_1,w_2$ be 2 vertices in $V \setminus V_A$. Then $w_1,w_2$ do not form an edge.

Otherwise $M^*+\{w_1w_2\}$ would be a larger matching in $G$ than $M^*$, contradicting $M^*$ is maximum.

So we now give a proper coloring $$c: V \mapsto \{1,2,\ldots,k-1\}:$$ Let $c$ assign each of the $2k-1$ vertices in $V_A$ one of $2k-1$ colors so that no 2 vertices in $V_A$ are colored the same color. Then for each $w \in V\setminus V_A$, let $v$ be a vertex in $V_A$ that is not adjacent to $w$; there exists such a $w$ by Claim 1; and set $c(w)=c(v)$. Then by Claim 2 this is indeed a proper coloring of $G$.

Related Question