I am searching for a tight lower bound (or a condition) for the number of edges of a graph with $n$ vertices such that if $E&gt;lower bound$ (or another condition) holds then the graph always contains a square ($C_4$). I would also appreciate a proof or a reference for the proof. Thanks a lot in advance!
122762
Square free graph : Graphs with minimum cycle length greater than 4.  Question : What is the maximum number of edges possible for a square free graph $G(V,E)$ given that $|V|$ = n. Is it of the order $O(n^2)$?  How does the answer change if max_degree(G) = d ($&gt;1$)?  EDIT: Out of curiosity, what is the maximum number of edges with $n$ vertices, when  we limit the  of the graph to $l$.  Thanks in advance!
81847
Can anybody give me any hints about how to prove that for any graph $G$ the number of edges in it is at least $\chi(G)(\chi(G)-1)/2$?  $\chi(G)$ is the minimal number of colors we need to use to color the graph (it's chromatic index in other words).  I tried induction but I'm stuck at an induction step.  I do the induction on the number of edges.  When $|E(G)|=0$ then obviously we can color the graph using only one color, so the theorem holds.  Now induction step from $n \Rightarrow n+1$ edges.  Let's erase any edge $e=\{v,u\}$ from $G$. Then $\chi(G-e)$ is either the same, or $\chi(G-e)&lt;\chi(G)$, because we relaxed the graph an $v$ and $u$ no longer need to have different colors. From the first case the thesis is clear, because $G-e$ has more then $\chi(G)(\chi(G)-1)/2$ edges so with the one we erased it's still more. But from the second case we only know that $G \geq \chi'(G)(\chi'(G)-1)/2$ and $\chi'(G)(\chi'(G)-1)/2 \leq \chi(G)(\chi(G)-1)/2$ so that gives me nothing...
29021
I'm looking to prove that any $d$-regular bipartite graph satisfies the HALL condition and contains a perfect matching.  I'm having trouble seeing why, if $G=(V,W,E)$, for any $H \subseteq V$, $|H|\leqslant |N(H)|$.  Would appreciate an answer!   Edit: For degree $\geqslant 1$ obviously.
1134
I am given this problem: Suppose you have a complete graph with $n$ edges. How many vertices does your graph have?  I have this math figured out so far: We know that a complete graph has $m$ vertices, with $m-1$ edges connected to each. This makes the sum of the total number of degrees $m(m-1)$. Then, since this sum is twice the number of edges, the number of edges is $\frac{m(m-1)}{2}$.  But I don't think that is the answer. I think I am missing a piece of the math, but I can't figure out what else I need to do. Can anyone help me with what I'm missing or doing wrong?
36156
Show that a graph $G$ contains a triangle (1) if and only if there exist indices $i$ and $j$ such that both the matrices $A_G$ and $A^{2}_{G}$ have the entry $(i, j)$ nonzero, where $A_{G}$ is the adjacency matrix of $G$ (2).  $1 \implies 2$  If the graph contains a triangle, the entries in the matrix which correspond to edges between the vertices that that make up the triangle will be non-zero.  Each such pair $(i,j)$ will also be non-zero in $A^{2}_{G}$, because there is a path of length two between $i$ and $j$ (within the triangle), starting from $i$, using another vertex $k$ and ending in $j$.  $2 \implies 1$  If $(i,j)$ is 1 in $A_{G}$, then the vertices $i$ and $j$ must be connected. Furthermore, if $(i,j)$ is 1 in $A^{2}_{G}$ that means there must be some other vertex $k$ through which we can go to $j$ starting from $i$. Hence the edges $(i, j)$, $(i, k)$, $(k, j)$ makes up the triangle.  I had trouble writing down this proof properly. Is the main idea correct?
61044
It is an exercise on a book again. If a simple graph $G$ has 11 or more vertices,then either G or its complement  $\overline { G } $ is not planar.  How to begin with this? Induction?  Thanks for your help!
24047
Prove that every graph in which each vertex has degree at least 2 must contain a cycle.  I know that a vertex is a node and the only way for it to have a cycle is that when there are three vertices and three edges and that the shape is of a triangle. However I dont know how to prove it.  Thanks in advance
89481
Suppose that we had a set of vertices labelled $1,2,\ldots,n$.  There will several ways to connect vertices using edges. Assume that the graph is simple and connected.  In what efficient (or if there is no efficient way, you can just tell me whatever procedure you can think of) way do we be able to calculate the number of possible ways the graph can be made? (even if some graphs are isomorphic to each other, they are counted as separate cases.)
92153
Graph $G$ has the diameter greater than $3$. Prove that the diameter of   $G'$ (the complement graph) is less than $3$.   What I was thinking about:  $G$ has the diameter greater than $3$ $\implies$ $G$ has not less than $4$ vertices.  If the $u$ and $v$ are vertices in $G$ that represents the diameter, then in $G'$ there is the edge $uv$. So, I was thinking that only first neighbors can be the diameter of $G'$. We need to prove now that between every two neighbors in $G$ there is only one other vertex in $G'$ which connects these two vertices (so the diameter is less than $3$).
51280
I have to show that the edges of a complete graph on $n$ vertices for even $n$ can be partitioned into $\frac n2$ edge disjoint spanning trees.   I know that a complete graph has $\frac{n(n-1)}{2}$ edges. And for reference, a spanning tree is a tree on all $n$ vertices, so it has $n-1$ edges. But I don't know how to show my statement.
35990
What are common lower bounds for ${{2n} \choose {n}}$?    Edit:  I made a mistake in my original question.  It doesn't change my question but there is no reason for me to include the mistake.
86634
While discussing the question I had asked , @NealYoung and I encounter another problem, which is to judge complexity of the problem below:     Given a connected undirected graph, finding a maximum-size subset of   the edges such that every vertex has degree at most two.   I have found some paper on complexity of relative problems. Most of them added more constraint on the original one.  added "with no odd cycles" and proved that it is NP-hard.  implied that the variant added "with no 3-cycle" is P referring to another paper (which I failed to find). But I have been unable to judge complexity of the original problem. So how to judge it? Thanks.
56547
My actual question is to find the number of transversal given a collection of set ...  After a little bit of study it has come down to:  How can we count the number of matchings in a bipartite graph with parts of size $m$ and $n$ such that it covers all $m$ vertices of the first part, $m \le n$?  I already know that there is a way to count the number of perfect matchings in a bipartite graph with $m=n$ using the permanent of its (square) incidence matrix.
117923
Let $G = (V, E)$ be a cycle of length $4n$ and let $V = V_1 \cup V_2 \cup  ... \cup V_n$ be a partition of its $4n$ vertices into n pairwise disjoint subsets, each of cardinality 4. Is it true that there must be an independent set of $G$ containing precisely one vertex from each $V_i$? (Prove or supply a counter example.)  I think this is not right because just consider square with four vertices and four edges,but I have doubt that it is proper counter example.please help with your knowledge,thank you very much.    actually this is exercise 4 of chapter 5 from alon spencer probabilistic method.so I also tag this question as mentioned.
106663
Let $G$ simple connected graph on $n$ vertices and assume that both $G$ and $G'$(complement) are planar.   $m$ and $m'$ be the number of edges in $G$ and $G$.   $m+m'$ $=$ $n(n-1)/2$  $m, m'$ $≤ 3n − 6$  $m+m' ≤6n−12$  $n(n−1)/2 =m+m' ≤6n−12$  $⇒$ $n^2 −13n+24≤0$ $⇒$ $n&lt;11$.  Would this be a correct solution?  I have also noticed this only works for connected graphs so I was wondering how would I expand it to disconnected graphs?  Any help would be really appreciated.
79628
Show ${1\over n}\sum|S_i|=O(\sqrt n)$  where $S_i\subset [n]$, $|S_i\cap S_i|\le 1$ for $i\ne j$. A previous question required showing  $|E|\le {1\over 2}(\sqrt{t-1}n^{3\over 2}+n)$, for an $n$-vertex graph $G$. What I tried to do is placing $S_1,...,S_n$ in a row, and below it setting $1,...,n$ likewise. While I didn't mind the fact that as a graph, $S_i$ cannot be connected to $S_j$ as it will have no meaning here, I did pay attention to the restrictions I am given: I can't have a $K_{2,2}$ graph (also not a $K_{2,t\ge 2}$, but $t=2$ is tighter.). Is what I am doing admissible? If so, I am arriving at: $|E|\le {1\over 2}(\sqrt 2n^{3\over 2}+2n)$. Acknowledge(or at least assuming) that the number of edges is simply the sum of $|S_i|$'s, I get ${1\over n}\sum|S_i|\le  \sqrt2n^{1\over 2}+2$ which seems $O(\sqrt n)$. Is it graph theory acceptable arguing? I would really appreciate your insights.
51858
I'm asked the following quesiton:       Show that if $n\geq 3$, the complete graph on $n$ vertices $K_n$ contains a Hamiltonian cycle.     This seems obvious since $K_n$ contains a subgraph which is a cycle graph hitting all $n$ vertices. What am I missing here?