Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Isn't the complete graph on four vertices a counterexample to the assertion that there are two edge-disjoint circuits? –  user83827 Oct 12 '11 at 18:21
    
Yes, I was mistaken and edited the question. –  Listing Oct 12 '11 at 18:43
1  
I don't think the authors are claiming that a graph with $n < 10$ vertices has two edge-disjoint circuits (as ccc points out, this is false). Their theorem is that any (multi)graph $G$ with $n$ vertices and $n+4$ edges contains two edge-disjoint circuits. As their first step, they prove that it suffices to show that $G$ has a circuit with at most 4 edges, and the "well known and easy" statement is that this holds when $n < 10$. –  Nate Eldredge Oct 12 '11 at 18:46
    
Yes, thank you for pointing it out. –  Listing Oct 12 '11 at 18:57

2 Answers 2

up vote 4 down vote accepted

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)$.

share|improve this answer

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.

share|improve this answer
    
I underestimated the power of the fast that there is only a finite amount of vertices, thank you. Do you have any idea how he concludes the fact with the circuits? –  Listing Oct 12 '11 at 18:10
    
There must be some further restriction. A graph with two vertices and three edges connecting them does not have two edge-disjoint cycles. –  Ross Millikan Oct 12 '11 at 18:24
    
Sorry, the result is immediate as the case where they are short circuits has already been handled by him before :-) –  Listing Oct 12 '11 at 18:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.