Prove that all graphs with Degree Sequence $(2,2,2,2,2,2,2)$ have an odd cycle.

Question

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.

Answer 1

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.

Answer 2

If $G$ is connected then it is Eulerian and since each vertex has degree 2 it is also Hamiltonian i.e. it is $7$ cycle.

If $G$ has 2 conected components then one has $3$ and the other $4$ vertices and so they are $C_3$ and $C_4$ and we are done.

Clearly $G$ can not have $3$ or more connected components since each has at least $3$ vertices.

So we are done.

Answer 3

Let us try to make the graph , renaming the Nodes to $1,2,3,4,5,6,7$ , & let us try to make it Non-Bi-Partite.

Let Node $1$ be in Partition $P1$.
It is connected to Node $2$ & Node $3$ in Partition $P2$.

Let Node $2$ be connected to Node $4$ in Partition $P1$.
Now , [ Case A ] Node $3$ can be connected to Node $4$ (which will make a cycle) or [ Case B ] it can be connected to Node $5$ (which still keeps it open).

In Case A , we are left with Nodes $5,6,7$ , which will have to form a triangle with Cycle length $3$ , which is Non-Bi-Partite.

In Case B , let Node $4$ be connected to Node $6$ in Partition $2$.
Then [ Case B1 ] , Node $5$ is also connected to Node $6$ (which will make a cycle) or [ Case B2 ] it can be connected to Node $7$ (which still keeps it open).

In Case B1 , Node $7$ is left over unconnected , hence Degree is not $2$.
In Case B2 , Node $6$ will have to connect to Node $7$ in Same Partition $P2$ , hence that will not be Bi-Partite.

Over-all :
Case A : Non-Bi-Partite
Case B1 : Degree mismatch
Case B2 : Non-Bi-Partite

Hence we can not make it Non-Bi-Partite.

OBSERVATION :

Same thing applies to all Degree Sequences with ODD number of $2$ ( Eg $2,2,2,2,2,2,2,2,2,2,2,2,2$ )
When we have EVEN Number of $2$ ( Eg $2,2,2,2,2,2,2,2,2,2,2,2,2,2$ ) , we can make it Bi-Partite.
Proof is easy when involving Induction.

Alternate Proof without Induction : ODD Case : When-ever we make a cycle of $2n+2$ (4 , 6 , 8 , Etc) Nodes , we will be using $2n+2$ Nodes. We will eventually be left with $3$ Nodes (triangle Nodes with Degree $2$) or with $1$ Node (Degree $0$) , hence we can not make it Bi-Partite.
EVEN Case : We can always make a cycle of $2n+2$ (4 , 6 , 8 , Etc) Nodes , such that nothing will be left over , hence we can make it Bi-Partite.

Answer 4

If there are no odd cycles, then there are 3 possibilities. 1) G is a tree, 2) G has C4 cycle, 3) G has C6 Cycle

1. G is not a tree because there is no leafs in it's degree sequence.
2. Assume that G has a C4 cycle, then the remaining 3 nodes have to make a C3 cycle.
3. Assume that G has a C6 cycle, then one node will be left alone with no way to have two edges.