I've been asked to prove that a graph with Degree Sequence $(2,2,2,2,2,2,2)$ [2-regular, 7 vertices] cannot be bipartite.
I know that bipartite graphs cannot have any cycles of odd length.
I'm fairly certain that the only two graphs that fit the Degree Sequence is either $C_7$ or $C_4$ disconnected from $C_3$.
Both of these contain a cycle of odd length, so they cannot be bipartite.
But I'm not sure how to prove that all graphs with this Degree Sequence must contain a cycle of odd length.
Best Answer
Assume that there is a bipartite graph that has that cycle sequence. Then the $7$ nodes can be partitioned into 2 sets $A,B$ such that the only edges that exist are between a node in $A$ and a node in $B$.
Let's count the number of edges of that graph!
Since each edge has exactly one of it's nodes in $A$, that means there are exactly as many edges as the sum of the degrees of nodes in $A$, that is $2|A|$.
But the same is true for the set $B$, so the number of edges is also $2|B|$. That means $|A|=|B|$, but we also have $|A| + |B| = 7$ ($A$ and $B$ are disjoint and contain together all $7$ nodes).
This is of course impossible, so we have found a contradiction to such a bipartite graph with the given degree sequence existing. The proof only uses that the number of nodes is odd, so easily generalizes to any odd number of nodes.