3
$\begingroup$

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?

  • 0
    Oh right. My course is in a different language, so some things might be off. But I just mean a simple graph yes2011-12-12

2 Answers 2

5

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

  • 0
    @Ken, the first 9 comes from the vertex of degree at least 6, as it has degree at most 9.2014-12-08
1

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.