Question #2d377

1 Answer
Nov 24, 2016

The graph is not bipartite.


A bipartite graph is possible if the graph coloring is possible using two colors such that vertices in a set are colored with the same color. After, grouping the vertices in two sets, if those vertices in each set are not interconnected, then the graph is bipartite.

Attached a graph realization with the same degree sequence with coloring. We can verify that it is not bipartite, because we can group #{1,2,3}# in one set and #{4,5,6,7}# in another set, but the vertices in this last set are interconnected.

Note also that vertices {6,7} are conected each to the remaining.

enter image source here

Follows an example of a bipartite graph

enter image source here