[Math] A graph and its complement are paths

Question

i am new to graph theory and in one of the lectures notes i found a lemma about the paths of a graph and its complements?

LEMMA:There are only two graphs such that their complements are also paths:The path on 2 nodes on three vertices and the path on 4 nodes

i really don't understand this lemma, Can someone please explain the proof and what it means?

Thanks in advance

Answer 1

The complement of a graph is what you get when you replace (a) all the edges with non-edges, and (b) all the non-edges with edges.

So, here's the 4-node path and its complement:

The complement also happens to be a path.

The complement of a path on 2 nodes is the null graph on 2 nodes (i.e., 2 nodes, no edges), drawn below. This would generally not be regarded as a path, so this is an error in the statement given.

If the single vertex graph is considered a path, then its complement is also a path.

So probably the statement should be:

There are only two paths such that their complements are also paths: the path on 1 node, and the path on 4 nodes.

Oh, and the proof is essentially: (a) check small cases, then (b) for $n \geq 5$ nodes, the complement has a vertex of degree $ \geq 3$, so cannot be a path.