Let G be a simple graph such that \mathrm{diam}(G) \geq 3. Then \mathrm{diam}(G^c) \leq 3. Moreover, if \mathrm{diam(G)} > 3 then \mathrm{diam}(G^c) < 3.

Reminders: G^c is the complement graph,  so V(G) = V(G^c) and e \in E(G^c) \iff e \not \in E(G). \displaystyle \mathrm{diam(G)} = \max_{v_i, v_j \in V(G)} d(v_i, v_j). For example, \mathrm{diam}(K_n) = 1.


One thought on “3

  1. gciruelos says:

    Let u,v be two vertices in G such that d(u,v) \geq 3 and let x,y be any two vertices of G. Then x is adjacent to at most one of u,v, because otherwise we would have a path of length 2 between u and v. The same happens to y.
    WLOG we assume that x is not adjacent to v in G. If y is also not adjacent with v then xvy is a path of length 2 in G^c.
    If y is adjacent to v in G then y is not adjacent to u in G and then xvuy is a path of length 3 in G^c.

    We have shown that any two vertices x,y of G^c are at distance \leq 3.

    For the second part, assume the contrary and use the first part, noting that G^{c^c} = G.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s