It is known that the chromatic number of a complete graph is equal to the number of its vertices,  that is $\chi(K_n)=n$. My question is can we get a graph $G$ not containing $K_n$ but with $\chi(G)\geq n$, for $n\geq 3$?
121821
I found this exercise in Bollobas: Modern Graph Theory "Construct a triangle-free graph of chromatic number 1526"  It is added not to use results from the chapter about Ramsey Theory.   Now my qestions:  (1) Is there a nice way to construct such a graph?  (2) If yes then what is so special about this specific graph?  My ideas:  Grötzsch's theorem states that every triangle-free planar graph may be 3-colored, so we know that we can exclude planar grpahs and focus on non-planar graphs.  I read something about the Mycielskian on   I think this is the key to the solution but I do not see how to follow a concrete construction.
27397
So I need to count how many Eulerian cycles exist in the complete graph $K_{n,2}$. Two cycles are considered identical if:  1) The order of the edges is identical in both cycles. For example: The cycles $cabc, bcab, abca$ are identical.  Or  2) If we get the first cycle by reversing the order of the edges in the second cycle. For example: $abca$ and $acba$ are the same cycle.  Note: The order of the edges is what matters, not the vertices. Also, of course if $n$ is odd, there's no such cycle.  So I tried this in different ways and arrived at different solutions:  I can think of this as all the permutations of the side with $n$ vertices, removing all the reverse permutations, so that's $\frac {n!}{2}$.  Or, I can think of it as permutations in a cycle, which means $\frac {(n-1)!}{2}$.  Then I manually counted the Eulerian cycles in $K_{2,4}$ and I got 6, which works well with $(n-1)!$. So either I counted incorrectly, or $(n-1)!$ is the answer, but I don't understand why.  Any help would be appreciated.
39195
I need a pair of non-isomorphic graphs with the smallest n-vertex possibility and where degree sequences are the same. Is the minimum number 2, such as a multigraph with n=2? Please help with the reasoning on this question. Thank you!
107689
Color the edges of $K_6$ red or blue. Prove that there is a cycle of length 4 with monochromatic edges.  Attempt: I know that i have to...  prove that there must be TWO vertices with “red-degree” at least 3, or two with "blue-degree" at least 3. Call these U and V. (We'll assume we're in the red case; the blue case is similar.) Now, ask if they’re connected by a red edge, and how many red-adjacent neighbors they share. If you analyze this, there should be only a few cases to consider – and each should be relatively straightforward. For each case, you’ll show either that that case can’t actually happen in $K_6$, or that it gives rise to a monochromatic 4-cycle.
17573
It seems to me like the answer should be $n!$. Since you can first select the first vertex, then select each remaining vertex until you've got them all in a permutation.  My textbook, however, says that the answer is $(1/2)(n-1)!$  Unfortunately, it doesn't explain why this is. Why is it?
88986
I want to prove whether it is possible for a graph to have different degrees for each vertex. I think that it can be possible with an example, but I can't prove it with mathematics.
111535
Some preliminaries:   A matching in a bipartite graph with vertex set $X \cup Y$ is a subset $E_1$ of the edge set such that no vertex is incident with more than one edge in $E_1$  A complete matching in a bipartite graph is a matching such that every vertex in $X$ is incident with an edge in $E_1$.  A perfect matching in a graph $G$ (not necessarily bipartite) is a matching such that each vertex of $G$ is incident with one edge of the matching.  Theorem: A necessary and suﬃcient condition for there to be a complete matching from $X$ to $Y$ in $G$ is that $|Γ(A)|≥|A|$ for every $A ⊆ X$. Here $\Gamma(A)$ is used to denote the set of all neighbors of vertices in $A$.  Here's my proof. Can someone please verify it or improve it? I feel that it is a bit hand-waving and lacks much-needed rigor.     Show that a finite regular bipartite graph has a perfect matching   Let $X$ and $Y$ be the (disjoint) vertex sets of the bipartite graph. Let $A \subseteq X$. Then, there are $d|A|$ edges incident with a vertex in $A$. But then, $|\Gamma(A)| \geq |A|$. If that were not the case, then there would exist a vertex $v \in \Gamma(A)$ with $\operatorname{deg}(v) &gt; d$.  So, there exists a complete matching between the vertex sets $X$ and $Y$ of the bipartite graph. Note that this matching is perfect, since $|X| = |Y|$.
99945
I'm taking a first course in graph theory this semester and I'm working trough Graph Theory with Applications by J.A. Bonday and U.S.R. Murty. I can't find an answer to question 1.2.12(f):     (a) Show, using execise 1.2.5 that an automorphism of a simple graph $G$ can be regarded as a permutation on $V$ which preserves adjacency,and that the set of such permutations form a group $\Gamma(G)$ (the automorphism group of $G$) under the usual operation of composition.      (e) Consider the permutation group $\Lambda $ with elements (1)(2)(3), (1, 2, 3) and (1, 3, 2). Show that there is no simple graph $G$ with vertex set {1, 2, 3} such that $\Gamma(G)=\Lambda$.      (f) Find a simple graph G such that $\Gamma(G)\cong\Lambda$.
84427
Question:  Prove that for every tree $T$ and every integer $g$ there exists a graph $G$ without cycles of length up to $g$ and such that every two-coloring of the edges of $G$ contains a monochromatic copy of $T$.  Thoughts: I saw something similar here , but besides the $\mathrm{girth}(G)=g$, I couldn't find a way to connect the information into a start for a proof. Any Hints?  (This is similar to this  which has no answer)  added after trying to solve using hints in comment:  I have this idea for a proof - Want to verify I got this right as it still seems difficult. I'll use facts 1-4 from here  .    From fact 2 we have that exists a graph $G_{g,k}: \delta(G_{g,k})\ge k=|V(T)|$. From fact 3 we have that $G_{g,k}$ has a sub-graph H s.t $\delta (H)\ge\frac {|E(G)|}{|V(G)|}\ge k (***)$. From fact 1 we have that $H$ contains a copy of T. From fact 4 (pigeonhole) we have that $\frac {|E(G)|}{|V(G)|} \ge \frac {|E(H)|}{|V(G)|} \ge \frac{|E(G)|}{2|V(G)|}$ or $\frac {|E(G)|}{|V(G)|} \ge \frac {|E(G\setminus H)|}{|V(G)|} \ge \frac{|E(G)|}{2|V(G)|}$ A 2-coloring may be viewed as a partition of G to H (Blue) and H-complement (Red) therefore H or H-complement contains a copy of T - so we have G which has the required girth and it contains a monochromatic copy of T.   The only problem I have now is how to justify the (***) move.
121474
Problem. Use Tutte's 1-factor theorem to prove that every 3-regular graph with no bridges has a 1-factor.  I honestly have no idea how to approach this problem. I have drawn a couple of graphs to gain some insight to no avail. Any hints or tips will be greatly appreciated.
24053
i think if the graph G has an odd cycle, it's not two-colorable, otherwise it can be two colorable.   i read in one notes that the following is True: we couldent two-colorable any graph G that has cycle.    anyone could clarify me ?
2891
I'm having a bit of a trouble with the below question     Given $G$ is an undirected graph, the degree of a vertex $v$, denoted by $\mathrm{deg}(v)$, in graph $G$ is the number of neighbors of $v$.   Prove that the number of vertices of odd degree in any graph $G$ is even.
7307
I was reading up on a proof of Ramsey's Theorem and I can't understand this part of the proof:      Pick a vertex $v$ from the graph, and partition the remaining vertices into two sets $M$ and $N$, such that for every vertex $w$, $w$ is in $M$ if $(v, w)$ is blue, and $w$ is in $N$ if $(v, w)$ is red. Because the graph has $R(r - 1, s) + R(r, s - 1) = |M| + |N| + 1$ vertices, it follows that either $|M| \geq R(r − 1, s)$ or $|N| \geq R(r, s − 1)$.   Why is that $|M| \geq R(r − 1, s)$ or $|N| \geq R(r, s − 1)$? I know from the proof of $R(3,3) = 6$ that given a vertex, at least $3$ are guaranteed to be either red or blue, so what is the pigeonhole argument for the general case?
81124
How to find chromatic number the $n$-dimensional hypercube $Q_n$?  I know $\chi(Q_2)$=2 , $\chi(Q_3)$=2 , $\chi(Q_4)$=4
90533
Question I found in "Introduction to Graph Theory" by Douglas B. West:     Let $G$ graph on $n$ vertices with connectivity $\kappa(G)=k \geq 1$. Prove that $$n \geq k(\operatorname{diam}(G)-1)+2$$ where $\operatorname{diam}(G)$ is the the maximal (edge) distance between a pair of vertices in $G$   Seems easy and I've seen the answer, too, which goes the same as thought: by taking the vertices the end vertices of the path of length $\operatorname{diam}(G)$, and applying Menger's Theorem. I'm having a hard time understanding one part - it seems like all the paths need to be of the same length for the $n \geq k(\operatorname{diam}(G)-1)+2$ to apply. Am I missing some part here?
35509
This is again some homework translated (hopefully not too badly) from my book  The graph $K_{n}$ is colored using $n$ different colors, in a way that each color is used at least once. Prove that there exists a triangle with its edges colored in different colors.
112792
I'm struggling on this question and any hints (not full answers) would be greatly appreciated.  Consider Bipartite Graph G with vertex Classes A and B of the same size.  I need to use Hall's Theorem to show that is |N(S)| > |S| for all subsets S of A then for any edge e, G contains a perfect matching containing e.  Thanks!