problems about pigeonhole principle

Question

The only thing I can figure out is that I need to use pigeonhole principle. But I don't know how to build the holes in such problems. Any suggestion or hint is appreciated. Thanks!

Answer 1

The idea is to partition the nodes into groups of 2 or 3, so that any two nodes within a group are connected by an edge. For example, try grouping the nodes like the following (the nodes with same color are in the same group):

Can you argue from here that every group can have at most 1 node colored black?

Answer 2

In below images, the six green triangles cover all vertices except the one marked red. Hence either one of the green triangles has two of the eight black nodes (and we are done), or the red node in each case is black. But that gives us two adjacent black nodes!