complete k-partite graphsI am trying to solve the following problem:Let G be a nonempty graph with the property that whenever u v ∉ E ( G ) and v w ∉ E ( G ), then u w ∉ E ( G ). Prove that G has this property if and only if G is a complete k-partite graph for some k ≥ 2. (Consider 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.

Question

complete k-partite graphsI am trying to solve the following problem:Let G be a nonempty graph with the property that whenever   u  v  ∉  E  (  G  ) and   v  w  ∉  E  (  G  ), then   u  w  ∉  E  (  G  ). Prove that G has this property if and only if G is a complete k-partite graph for some   k  ≥  2. (Consider             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.

suchonos6r · Accepted Answer

(There was a typo in your problem, the conclusion of the property must be   u  w  ∉  E  (  G  ) (not   u  w  ∈  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   u  w 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.

Let G be a nonempty graph with the property that whenever u upsilon !in E(G) and vw !in E(G), then uw !in E(G). Prove that G has this property if and only if G is a complete k-partite graph for some k>=2. (Consider bar G).

Answered question

Answer & Explanation

New Questions in Descriptive Statistics