0
$\begingroup$

Is my proof for the following statement correct?

Any finite connected graph with every vertex has degree $\ge 2$ has a circuit.

My attempt: Let $G$ be a finite connected graph. Let $|G|=n$. Suppose that degree of any vertex $\ge 2$. Now, pick any vertex $v_1$. By hypothesis $v_1$ must have at least two distinct edges incident on it; pick one, call it $e_1$. Call the end vertex of $e_1$ different from $v_1$ as $v_2$. Now pick an edge $e_2$ different from $e_1$ incident on $v_2$. Let $v_3$ be the end vertex of $e_2$ different from $v_2$. If there is an edge joining $v_3$ and $v_1$, we are done. If not, pick any edge $e_3$ different from $e_2$ incident on $v_3$ and repeat the previous argument. Now, we proceed by induction and find vertices $\{v_1 , v_2, \ldots, v_n , v_{n+1} \}$ such that there is an edge between $v_i$ and $v_{i+1}$. Since $G$ is connected, the component of $G$. containing $v_1$ which is a superset of $\{ v_1, v_2, \ldots , v_{n+1} \}$ is equal to $G$. So, $v_{n+1}=v_1$ and hence we are done.

Is this proof correct? Is there an easier way to do this?

$\endgroup$
4
  • $\begingroup$ Simpler: assume the opposite. Then, G is a tree. A tree has at least one leave, which has degree 1. This is a contradiction. $\endgroup$
    – NeitherNor
    Jul 12, 2020 at 6:25
  • $\begingroup$ Btw, you should either exclude or separately treat the empty graph and the graph with one vertex... $\endgroup$
    – NeitherNor
    Jul 12, 2020 at 6:31
  • $\begingroup$ @NeitherNor I am trying to use this to prove that a tree with $n$ vertices has $n-1$ edges. $\endgroup$
    – ashK
    Jul 12, 2020 at 7:38
  • $\begingroup$ @NeitherNor there's nothing to prove in the case where $|G|=0$ and $|G|=1$ $\endgroup$
    – ashK
    Jul 12, 2020 at 7:45

3 Answers 3

1
$\begingroup$

There is no guarantee $v_{n+1}=v_1$. For example, take a "bow-tie" graph (i.e., two 3-cycles with a vertex in common) and start at $v_1$ any degree-2 vertex, $v_2$ the cutvertex and now only walk the other triangle for $v_3,v_4,v_5,v_6$.

Instead, note that $v_1,v_2,\dots,v_{n+1}$ are $n+1$ vertices from the set of $n$ vertices of $G$, so by pigeonhole there must be $1\leq i<j\leq n+1$ with $v_i=v_j$. By construction we know $j\neq i+1$ and so ...

$\endgroup$
2
  • $\begingroup$ You need to be just a little careful to establish that there is an unused edge that allows you to continue the construction. $\endgroup$ Jul 12, 2020 at 6:25
  • $\begingroup$ @RobertShore The OP's construction already established that. The only final touch in the "..." is a minimality argument to deal with the possible case $v_iv_{i+1}$ and $v_{j-1}v_j$ are the same edge.. $\endgroup$ Jul 12, 2020 at 6:31
1
$\begingroup$

Let $P:=v_0,\ldots,v_n$ be any maximal path in $G$. Since $P$ is maximal, $P$ cannot be extended. So every neighbour of $v_0$ must be a vertex in $P$. Since $d(v_0)>1$, there exists a vertex $v_k$ in $P$ such that $v_k \leftrightarrow v_0$ with $k>1$.

Let $\ell$ denote the least $k>1$ such that $v_k \leftrightarrow v_0$. Then the $v_0-v_{\ell}$ path on $P$ followed by the edge $v_{\ell}v_0$ is a cycle in $G$. $\blacksquare$

$\endgroup$
0
$\begingroup$

I think you have the right idea but the proof isn't quite correct because it's not necessarily the case that $v_{n+1}=v_1$. I'd go a little simpler.

Assume $\vert G \vert = n$. Start at $v_1$. Proceed inductively. If there are no unused edges from $v_m$, then you've necessarily been at both $v_m$ and its predecessor at least once before so you have a cycle. Otherwise, choose an unused edge from $v_m$ to reach vertex $v_{m+1}$. Continue until you've reached $v_{n+1}$. By the pigeonhole principle, two of your vertices $v_m, v_{m+k} ~(k \gt 1)$ must be the same, so again you have a cycle.

$\endgroup$

You must log in to answer this question.

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