I am trying to solve the following problem:

Let $G$ be a nonempty graph with the property that whenever $uv \notin E(G)$ and $vw \notin E(G)$, then $uw \notin E(G)$. Prove that $G$ has this property if and only if $G$ is a complete $k$-partite graph for some $k \geq 2$. (Consider $\bar{G}$).

The converse is straightforward and is given by the definition of the complete k-partite graphs, however, the direct way is not trivial and I could not get it. Any helps? :)


(There was a typo in your problem, the conclusion of the property must be $uw\notin E(G)$ (not $uw\in E(G)$).

First of all, each complete $k$-partite graph has this property, as you say.

To show the inverse, assume the property (whenever $uv$ and $vw$ are not edges of $g,$ then $uw$ is not an edge). Consider the relation on the vertices where two vertices are related if there is no edge between them (or if they are identical). This is an equivalence relation, where transitivity follows from the given property.

Per definition, given a pair of vertices from different equivalent classes there must be an edge between them. Thus, $G$ is a complete $k$-partite graph, where the decomposition of the vertices into sets (as required by the definition) is given by the equivalent classes.

  • $\begingroup$ Thank your for your prompt response and thanks for bringing that typo to the attention. As far as I understood from your response, you considered graph $\bar{G}$ where the the relation you defined holds true. Now, if $\bar{G}$ is a complete k-partite graph, is $G$ also a k-partite graph? $\endgroup$ – Morteza Soltani Dec 12 '17 at 6:59
  • $\begingroup$ Well, I wouldn't have phrased it with $\bar G.$ My logic is simply to observe that grouping the vertices into equivalence classes gives you the property of a $k$-partite graph (defined as in the Wikipedia). In a way, the equivalence is almost tautological. $\endgroup$ – Reiner Martin Dec 12 '17 at 7:04

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.