Triangle-free graph

A triangle-free graph is a special type of picture made up of dots (called vertices) and lines (called edges) connecting them. It is called triangle-free because there are no three dots that are all directly connected by lines to each other.

Think of playing with blocks. If you have three blocks placed in such a way that they are all touching each other, you can't move one block without moving the others too. In the same way, if you have a picture of dots connected by lines that form a triangle, you can't remove one line without disconnecting two dots and making a triangle.

Triangle-free graphs are important in mathematics and computer science because they have some interesting properties. For example, they are easier to color (you can color each dot a different color without any two connected dots being the same color) and they have fewer potential connections between sets of dots.

Next time you draw a picture of dots and lines, try to make a triangle-free graph!