0
$\begingroup$

I am trying to intuitively understand why a bipartite graph in which every vertex has degree exactly $2$ is simply a cycle. So far, I have tried to intuitively justify this by saying that an Eulerian tour exists due to the graph being even degree, and that it is connected as the number of vertices is equal to the number of edges, meaning this is a tree with another edge added (I am quite unsure about this rationale behind connection). However, an Eulerian tour isn't the same as a cycle as a cycle can't contain repeated vertices but an Eulerian tour can. I know that if an Eulerian tour exists, a cycle exists in the graph by eliminating repeated edges in the Eulerian tour, but this is different than saying that the entire graph (without deleting edges) constitutes a cycle. So how can I intuitively justify why a bipartite graph in which every vertex has degree exactly $2$ is simply a cycle?

EDIT: the solution to a problem I am trying to understand says:

we have a bipartite graph where every vertex has degree d = 2. This means that the graph is just a cycle of even length, which is a case that we’ve already covered in the first part.

The first part of which they spoke was showing any cycle of even length can be 2 colored, and the context is that we are showing that any bipartite graph wherein the vertices have degree exactly $2^k$ can be edge-colored using $2^k$ colors, by induction on $k$ and above they are talking about the base case. I am confused about this statement and am wondering how to make sense of it in light of what comments and answers have said about the claim in my question being false.

$\endgroup$
4
  • 3
    $\begingroup$ a graph (not necessarily bipartite) in which every vertex has degree exactly 2 is a collection of disjoint cycles, not necessarily a single cycle. $\endgroup$
    – caduk
    Commented Oct 7, 2023 at 9:32
  • 1
    $\begingroup$ What you are asking about is not true. A graph consisting of two disjoint 4-cycles is a counterexample. You have to assume the graph is connected to get the result you want. $\endgroup$ Commented Oct 7, 2023 at 9:33
  • $\begingroup$ @caduk how would we show that it is necessarily a collection of disjoint cycles? $\endgroup$ Commented Oct 7, 2023 at 9:56
  • 1
    $\begingroup$ @Shmuel Given an edge of the graph, if you walk the graph, the path is uniquely determined (there is always one direction that does not go backward) and you must loop back to the other extremity of the starting edge (otherwise if you reach another visited vertex, this vertex would have degree at least 3), so the corresponding connected component is formed of a single cycle, hence it is a cycle graph. $\endgroup$
    – caduk
    Commented Oct 7, 2023 at 10:25

1 Answer 1

1
$\begingroup$

This question is simply not true, since there are the existence of disconnected bipartite graphs. The graph of two disjoint 4-cycles is a simple counterexample of this.

If we assume that the graph is connected, then the requirement of the bipartite graph is unneeded, as this new condition alone suffices to prove that the graph is a cycle. We can just consider a walk for this proof.

If we are trying to prove that the graph must contain a collection of cycles, we can separate the graph into connected pieces. Since subgraphs of a bipartite graph are also bipartite, and we know that each individual graph is complete, we can deduce that each individual graph is cycle, and therefore the whole graph is a collection of cycles.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .