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

  • $\begingroup$ 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. $\endgroup$ – 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 4-node path

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.

2-node path and its complement

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.

  • 1
    $\begingroup$ 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. $\endgroup$ – bof May 10 '15 at 10:31
  • $\begingroup$ @rebecca the statement is as mentioned , i will clarify the first part with my colleagues !! Thanks for answering fast !! $\endgroup$ – Kiran Mathews May 10 '15 at 22:01

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.