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.

Let $G = (V(G),E(G))$ be a singular graph with $n=10$ and $|E|= 28$. Show that $G$ contains a cycle of length $4$.

The question says it all. Our teacher gave us the hint that it is similar to another question that we answered using combinatorics and double counting techniques with properties of singular graphs. (in that case: we had $G' = (V(G),E(G))$ singular, with $n=10$ and $|E|=38$, show that $G$ contains $K_{4}$.)

But I don't know how to solve this one, I don't know how to start with this proof. What is the best way? Constructive proof where we draw the graph and show that we avoid having a cycle of length $4$ and that eventually, you have to have a connection which gives length $4$ or is this solveable in other ways?

share|improve this question
3  
What is a singular graph? –  Gerry Myerson Dec 11 '11 at 22:13
2  
Probably simple. –  N. S. Dec 11 '11 at 22:22
    
@Gerry: Googling indicates that singular graph can mean graph whose adjacency matrix is singular. However, that seems a bit more sophisticated than the level suggested by the post. –  Brian M. Scott Dec 12 '11 at 5:31
    
Oh right. My course is in a different language, so some things might be off. But I just mean a simple graph yes –  froginvasion Dec 12 '11 at 18:33

2 Answers 2

up vote 3 down vote accepted

If N.S. is right, and "singular" means "simple", then this might be the start of an answer.

First note that there must be at least one vertex of degree at least $6$, for, if every vertex has degree at most $5$ then there are at most $10\times5/2=25$ edges, contradiction.

Now suppose there are two vertices of degree at least $6$. Call them $A$ and $B$. Each must be adjacent to at least $5$ of the other $8$ vertices, hence, there must be at least $2$ vertices that are adjacent to both $A$ and $B$. If we call those two vertices $C$ and $D$, then $ACBDA$ is a cycle of length $4$.

So it remains to do the case where there is only one vertex of degree at least $6$. My guess is you can show something like this: there must be two vertices of degree adding up to $12$ or more, and then use an argument like the one for the previous case.

EDIT: Yes, I think we can finish this off. Suppose there's only one vertex of degree at least $6$. You can't have one of degree at least $6$ and the other nine of degree at most $5$ as a similar calculation to the earlier one shows you wouldn't get $28$ edges ($9+9\times5=54\lt2\times28$). You must have at least two vertices each of degree at least $6$, and the proof goes through.

MORE EDIT: The result is ridiculously far from being sharp; 28 can be replaced by 17. That is, there is a 10-vertex, 16-edge graph with no 4-cycle, but every 10-vertex graph with 17 (or more) edges has a 4-cycle. See https://oeis.org/A006855

share|improve this answer
    
thank you very much for this answer! I found the answer too, but it is interesting to see the reasoning behind it, as that is the key to understanding. –  froginvasion Dec 12 '11 at 18:35
    
can you explain the calculation (9 + 9 x 5 = 54 < 2 * 28)? where does the first 9 come from? –  Ken Vernaillen Dec 8 at 20:35
    
@Ken, the first 9 comes from the vertex of degree at least 6, as it has degree at most 9. –  Gerry Myerson Dec 8 at 22:18

geng, which comes with nauty can exhaustively enumerate the $10$-vertex $28$-edge graphs without $4$-cycle (not necessarily induced) subgraphs via:

geng 10 28:28 -f

which returns

>A geng -fd0D9 n=10 e=28
>Z 0 graphs generated in 0.00 sec

In fact, it turns out that $17$ edges are sufficient to ensure the existence of a $4$-cycle subgraph. Up to isomorphism, there are two $10$-vertex graphs with $16$ edges and no $4$-cycle subgraphs, drawn below:

enter image description here

It is possible for a $10$-vertex $28$-edge graph to have no induced $4$-cycles. For example, $K_8$ together with two isolated vertices has $10$ vertices, $28$ edges and no induced $4$-cycle.

share|improve this answer

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.