whether for a k-chromatic connected graph on n vertices,every pair of distinct coloured vertices are joined by atleast one path of odd length when the graph is coloured with exactly k number of colours!
2026-05-14 17:48:47.1778780927
On path between two vertices of diffenent colour.
135 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
The statement is trivially true when $k=2$, since this implies that the graph is bipartite.
It is not true when $k>2$ as you can easily see when you take a $K_k$ with a $P_3$ attached. Since you have more than two colors you can construct a coloring where the two endpoints of the $P_3$ have different colors, but nevertheless the only path between them has even length.
However, in this counterexample we could have colored the two endpoints with the same color. Because your writeup of the question is not very robust, you may have wanted to ask the following, slightly more interesting question.
If two vertices $v$ and $w$ have different colors in every possible $k$-coloring, is there always a path of odd length between them?
In this case the answer is 'yes', which can be seen by looking at the Kempe-subgraph containing $v$ and $w$ (i.e. the subgraph containing all vertices having the same color as either $v$ or $w$).
If $v$ and $w$ are in different components then you can swap colors on one of those components and obtain a proper $k$-coloring where $v$ and $w$ have the same color. Contradiction.
So $v$ and $w$ are in the same component. Since this component is bipartite and $v$ and $w$ are in different partite sets every path between $v$ and $w$ in this component is odd.