# A graph and its complement are paths

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?

• What does "path on 2 nodes on three vertices" mean? What's the difference between nodes and vertices? I thought they were different names for the same thing. – bof May 10 '15 at 10:34

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.

• Or, since a path on $n$ vertices has $n-1$ edges, and since the complete graph on $n$ vertices has $n(n-1)/2$ edges, you could solve the equation $2(n-1)=n(n-1)/2.$ The solutions are $n=1,4,$ so $n\in\{1,4\}$ is a necessary condition, and is easily seen to be sufficient as well. – bof May 10 '15 at 10:31
• @rebecca the statement is as mentioned , i will clarify the first part with my colleagues !! Thanks for answering fast !! – Kiran Mathews May 10 '15 at 22:01