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

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.

• You're right, one thing you can do to conclude is to show that every connected component of such graph is a cycle, and conclude that you listed all the possibilities. Commented Jul 31, 2023 at 4:07

## 4 Answers

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.

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.

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.

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.