Impossible to search, classic graph problem

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Impossible to search, classic graph problem

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Classic

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1004 posts

#1 h Mar 30, 2025, 5:19 PM

Y by

Prove that any graph $G=(V,E)$ with $|V|=|E|-1$ has at least two cycles in it.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

873 posts

#2 h Mar 31, 2025, 11:33 PM • 1 Y

Y by Captainscrubz

Claim 1. The problem reduces to the case when $G$ is connected.

Indeed, if $G$ consists of the connected components $H_1, H_2, \ldots, H_k,$ then there must be some $i$ such that $|E(H_i)| \ge |V(H_i)|+1.$ Otherwise, $|E|=|E(H_1)|+\ldots+|E(H_k)| \le |V(H_1)|+\ldots+|V(H_k)|=|V|,$ contradiction.

Claim 2. The problem reduces to the case when each vertex has degree at least $2.$

Indeed, by removing all the vertices of degree $0$ or $1,$ we end up with a graph for which $|E| \ge |V|+1$ (this is because each vertex removal causes at most one edge removal).

Claim 3. A connected graph in which every vertex has degree $2$ is cyclic.

We pick a vertex. There are two edges emerging from it; we choose one of them. This sends us to a new vertex, which again has two edges emerging from it: the one which we have just crossed and another one. We keep walking by always choosing the new edge. Since the graph is finite, at some point we must reach a vertex that we have already visited. This proves the existence of a cycle. Since this cycle forms a connected component, it must be the entire graph.

Now let's consider a connected graph $G$ whose vertices have degree at least $2,$ with $|V|=n$ and $|E|=n+1.$ By the handshaking lemma, the sum of the degrees of the vertices is $2n+2.$ The only ways this is achieved are: 1. all the vertices have degree $2,$ except for one which has degree $4$ ; or 2. all the vertices have degree $2,$ except for two which have degree $3.$

Case 1. All the vertices have degree $2,$ except for one which has degree $4.$

From Claim 3 we know that the graph contains a cycle. This cycle must contain the $4$ -degree vertex because otherwise the graph is disconnected. By removing all the vertices from this cycle, except for the $4$ -degree vertex, we obtain a connected graph in which every vertex has degree $2.$ According to Claim 3, this is a cycle, so we just found a second cycle in $G.$

Case 2. All the vertices have degree $2,$ except for two which have degree $3.$

Since $G$ is connected, there is a path between the two $3$ -degree vertices. We remove all the vertices from this path, except for the $3$ -degree vertices. In this way we obtain a graph in which every vertex has degree $2,$ so according to Claim 3 it is a cycle. Now by putting the removed path back, we prove that we obtain at least two cycles (in fact at least three).

Let's say the cycle obtained after removing that path is $v_1 - v_2 - \ldots - v_{i-1} - v_i - v_{i+1} - \ldots - v_{j-1} - v_j - v_{j+1} - \ldots - v_1,$ where $v_i$ and $v_j$ are the $3$ -degree vertices. Let $P$ be the removed path. Then we also have the cycles $v_1 - v_2 - \ldots - v_{i-1} - v_i - P - v_j - v_{j+1} - \ldots - v_1$ and $v_i - v_{i+1} - \ldots - v_{j-1} - v_j - \overline{P} - v_i.$ (overline to indicate that it is crossed backwards)

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a