graph theory
I have the following exercise to do but don't know how to approach it:
Let $G$ be a graph with $n$ nodes ($n \ge 2$), and where every node has degree at least $3$. Show that $G$ has a cycle of length $\le 2\cdot \lceil\log n\rceil$. And it allows me to consider a breadth-first search tree.
First of all, what's the length of a cycle? Is it the number of arcs in the cycle? Secondly, how do I show it's $2\cdot\lceil\log n\rceil$?
Thanks, Sorin
What you need is the following observation/result:
Proposition: A graph is bipartite if and only if the set of vertices/nodes can be partitioned into two subsets in such a way that in a given subset, no two vertices are connected.
Think about it a little while, and it should become clear. But then, you see that a graph without cycles is clearly bipartite. For if you have a tree, choose a root. Then you put this root in one set; you put its neighbours in the second set; you put the neighbours' neighbours in your first set, etc. Since there is no cycle, for any choice of two vertices in a given subset, they won't be adjacent. Now, if you have a forest, partition each tree separately.
This is the way I would prove that a forest is bipartite, but this is only because I am more familiar with the definition involving a partition of the vertex set. On the other hand, for vacuous reasons, a forest is bipartite, exactly because it does not have any odd cycle (since it does not have any cycle). However, sometimes it happens that we are reluctant to believe something is true for vacuous reasons. This is why I wrote the above solution.
There are $10$-vertex $15$-edge (and $3$-regular) graphs that are Hamiltonian. For example:
This essentially means that no proof can exist that only accounts for number of vertices and edges (or the degree sequence), since there are both Hamiltonian and non-Hamiltonian examples. Any proof must be able to separate the Petersen graph from the graph above. We also cannot expect to find a simple algorithm, since the problem is NP-complete.
There are some bugs in the argument: along with what Micah mentioned, there are instances where there aren't three vertices $a$, $b$ and $c$.
Best Answer
The length of a cycle is the number of vertices in the cycle (which is equal to the number of edges in the cycle). Some examples are given below:
Suppose we have a graph $G$ with $n \geq 2$ vertices and minimum degree $3$. Let $C$ be the shortest cycle in $G$, and let $x$ be a vertex in $C$. (Note: there exists at least one cycle in $G$, otherwise $G$ would be a forest, and non-empty forests have vertices of degree $0$ or $1$.)
Two slightly different situations can arise, depending on whether $C$ is an odd-length cycle or an even-length cycle.
To find the upper bound on $t$, we look at the neighbours of $x$, then their neighbours, and so on, until we first hit a cycle. This will occur at depth $\frac{t-1}{2}$, since $t$ is odd.
The situations is as depicted below, where the cycle in bold represents $C$.
Every vertex on level $i \in \{1,2,\ldots,\frac{t-1}{2}-1\}$ is connected to at least $2$ vertices on level $i+1$ and exactly $1$ vertex on level $i-1$. Any other situation would either imply (a) we have not accounted for all vertices at a given level or (b) there exists a cycle shorter than $C$. Therefore \begin{align*} n &\geq 1+\sum_{i=0}^{\frac{t-1}{2}-1} 3 \cdot 2^i \\ &=1+3 \cdot 2^{\frac{t-1}{2}} & \text{using the identity } \sum_{k=0}^a 2^a=2^{a+1}. \end{align*}
In this situation, the picture looks like the following:
And we can instead deduce \begin{align*} n &\geq 3+\sum_{i=0}^{\frac{t}{2}-2} 3 \cdot 2^i \\ &=3+3 \cdot 2^{\frac{t}{2}-1} & \text{using the identity } \sum_{k=0}^a 2^a=2^{a+1}. \end{align*}
Hence we have:
Proof: If $t$ is odd, then $$n \geq 1+3 \cdot 2^{\frac{t-1}{2}} = 1+\frac{3}{\sqrt{2}} \cdot 2^{\frac{t}{2}} \geq 2^{\frac{t}{2}}.$$ If $t$ is even, then $$n \geq 3+3 \cdot 2^{\frac{t}{2}-1} = 3+\frac{3}{2} \cdot 2^{\frac{t}{2}} \geq 2^{\frac{t}{2}}.$$ [End of proof.]
So, if $t>2 \lceil \log_2 n \rceil$, then, by the lemma, we have $$n > 2^{\log_2 n} = n$$ giving a contradiction. So finally, we can conclude:
It is worth noting that the bound can sometimes be achieved. For example, this is $K_{3,3}$:
which has $n=6$ vertices and the shortest cycle is a $2 \lceil \log_2 n \rceil$-cycle. It's not going to be "perfect" (since we rounded off in the lemma above), but it will be asymptotically the best possible.