So I have been trying to do research on this online, and all I see are a bunch of graphs with multicolored dots, and telling me to use those to determine if the graph is bipartition. The ones in the book do not have no color to them, so everything online is not really helping. From what I see, a bipartition graph is one that can be divided into two subsets.
Am I correct in saying that this graph is not bipartition because of the vertice in the middle of the square? Graph
There is a distinction between the terms bipartition and bipartite graph. A bipartite graph is a graph that contains a bipartition. A bipartition is two subsets of vertices that satisfy specific properties. When they give you multi-colored dots, my understanding is that they are asking if these two sets of dots form a bipartition. When there are no colors, the problem then should be whether the graph is bipartite. In other words, among all possible colorings, is there a coloring that forms a bipartition?
You have to be careful here when you argue that the graph is bipartite. Think of bipartitions this way: color some of the vertices red, and the others blue. Does every edge connect a red vertex to a blue vertex? If not, the coloring is not a bipartition. Repeat the process for all possible colorings to see if the graph is bipartite. For now, use your intuition to see if you believe there exists a satisfactory coloring.
For the graph given here, consider coloring the top-left and bottom-right vertices red, and the other three vertices blue. Then, every edge connects a red vertex to a blue vertex. So the sets of blue and red vertices form a bipartition. Thus the graph is bipartite.
