3
$\begingroup$

Lately I read an old paper by Paul Erdős and L. Pósa ("On the maximal number of disjoint circuits of a graph") and stumbled across the following step in a proof (I changed it a bit to be easier to read):

It is well known and easy to show that every (undirected) graph with $n < 10$ vertices, where all vertices have a degree $\geq 3$ contains a circuit of at most $4$ edges.

I would be very happy if someone could enlighten me how this is simple and why he can conclude that, maybe there are some famous formulas for graphs that make this trivial? For the ones interested, he also mentions that a counterexample for $n=10$ is the petersen graph.

  • 0
    Yes, thank you for pointing it out.2011-10-12

2 Answers 2

4

Because every vertex have degree $\ge 2$, there must be at least one cycle.

Consider, therefore, a cycle of minimal length; call this length $n$. Because each vertex in the cycle has degree $\ge 3$, it is connected to at least one vertex apart from its two neighbors in the cycle. That cannot be a non-neighbor member of the cycle either, because then the cycle wouldn't be minimal.

If the graph has $V$ vertices and $n > V/2$, then due to the pigeonhole principle two vertices in the cycle must share a neighbor outside of the cycle. We can then construct a new cycle that contains these two edges and half of the original cycle, and this will be shorter than the original cycle unless each half of the original cycle has length at most $2$.

Therefore, a graph with $V$ vertices each having degree $\ge 3$ must have a cycle of length at most $\max(4,\lfloor V/2\rfloor)$.

2

If you start from vertex 1, it must connect to at least three other vertices, which we can call 2,3,4. Then each one must connect to two more vertices which are none of the ones already named (or we would have a 3-circuit), so 2 goes to 5,6; 3 to 7,8; 4 to 9 and where? Anywhere it goes makes a 4-circuit.

  • 0
    Sorry, the result is immediate as the case where they are short circuits has already been handled by him before :-)2011-10-12