Given a simple Graph $G=(V,E)$ ($V$ vertices, $E$ edges) I have to show that there exists a distribution $V= V_1 \cup V_2$ of the vertices such that all vertices in the induced subgraphs $G[V_1]$ and $G[V_2]$ have even degree.  I honestly have no idea how to solve this question. I tried several things (which I will list below) but all attempts have failed.   induction: Induction on the number of vertices has proven to be extremely ugly for this  question, so I dropped the idea really quick. color all circles with odd elements first.  use that in $G$ there is an even amount of vertices with odd degree.   I do not want a complete answer to this question (at least not for the moment). Does anyone have an idea/tip for this question which doesn't give away too much?  I hope you can help me  slinshady
97358
I've got an example for this question, but there are many different possibilites and I don't know how to show this for all graphs. Has got anyone any advice how to begin ?  Let $G=(V,E)$ be an undirect graph. Then there is a partition $V = V_1 \cup  V_2$ of a vertices set, so that all vertices in $G[V_1]$ and $G[V_2]$ have got an even degree.  I draw it on paper, but how mentioned it, it's not proven for all and I don't know how. Thank you for any advice.
99259
I'm studying graph theory, coloring at the moment. I'm stuck with a proof of the following exercise: Let $G = (V, E)$ be a connected graph and let $v \in V$ be such that $deg(v)\lt d$. If $deg(w)\le d$ for all $w \in V-{v}$, then $G$ is $d$-colorable. I have an idea that I could use Brooks' Theorem but I'm not really sure. I'd appreciate it if someone could give me a hand here
24916
The problem: I'm trying to find the probability of a random undirected graph being connected. I'm using the model $G(n,p)$, where there are at most $n(n-1) \over 2$ edges (no self-loops or duplicate edges) and each edge has a probability $p$ of existing. I found a simple formula online  where $f(n)$ is the probability of $G(n,p)$ being connected. But apparently it's too trivial for the writer to explain the formula (it was just stated briefly).  The desired formula: $f(n) = 1-\sum\limits_{i=1}^{n-1}f(i){n-1 \choose i-1}(1-p)^{i(n-i)}$  My method is: Consider any vertex $v$. Then there's a probability ${n-1 \choose i}p^i(1-p)^{n-1-i}$ that it will have $i$ neighbours. After connecting $v$ to these $i$ neighbours, we contract them ($v$ and its neighbours) into a single connected component, so we are left with the problem of $n-i$ vertices (the connected component plus $n-i-1$ other "normal" vertices.   Except that now the probability of the vertex representing connected component being connected to any other vertex is $1-(1-p)^i$. So I introduced another parameter $s$ into the formula, giving us:  $g(n,s)=\sum\limits_{i=1}^{n-1}g(n-i,i){n-1 \choose i}q^i(1-q)^{n-1-i}$,  where $q=1-(1-p)^s$. Then $f(n)=g(n,1)$. But this is nowhere as simple as the mentioned formula, as it has an additional parameter...  Can someone explain how the formula $f(n)$ is obtained? Thanks!
40996
I'm trying to prove this by contradiction: if $G$ isn't complete graph, there must exist vertices $u,v \in V(G)$ for which edge $uv \notin E(G)$. Then $u$ and $v$ must have the same color in proper coloring $C$ and now I'd like to prove that by removing $u, v$ we have $\chi(G-u-v) = \chi(G) - 1$ (that would be the contradiction), but I'm not sure whether it's true.
34535
I was tasked to prove that when given 2 graphs $G$ and $\bar{G}$ (complement), at least one of them is a always a connected graph.  Well, I always post my attempt at solution, but here I'm totally stuck. I tried to do raw algebraic manipulations with # of components, circuit ranks, etc, but to no avail. So I really hope someone could give me a hint on how to approach this problem.
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!
20133
I am working on the following problem on 2-coloured complete graphs:     $K_9$ is coloured red and blue and contains no red triangle and no   blue $K_4$ then every vertex must have red degree 3 and blue degree 5.   Is this possible?   I am pretty sure the answer is 'no' but I am not sure how to explain my answer.  Any help would be greatly appreciated!
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.
87252
$G_1$ is graph on the set of vertices $\{1,2,3,4,5,6,7,8\}$, $G_1$ vertex chromatic number is 5. $G_2$ is graph on the set of vertices $\{7,8,9,10,11,12,13,14,15,17,18,19,20\}$, $G_2$ vertex chromatic number is 7. We know $G_1$ and $G_2$ have an edge between vertex 7 and vertex 8. (We already used 2 different colors on them both). $G$ is graph on the set of vertices $\{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20\}$, and its set of edges is the union of the edges set of $G_1$ with the edges set of $G_2$. The vertex chromatic number of $G$ is: 5 / 7 / 12 / we can't know without further information Prove the answer. I think I got it, can someone approve? After the union to $G$, we copy the colors of $G_2$ to 7,8,9,10,11,12,13,14,15,16,17,18,19,20, obviously, $G$ vertex chromatic number is 7 and can't be less. We go through the vertices 1,2,3,4,5,6,7,8. We look for a vertex that doesn't connect to a different vertex. (There must be one, because if only one edge was missing in $G_1$, our chromatic number of $G_1$ was 7, but it's 5). Once we find a missing edge, we color both its vertices in the same color. We go through vertices 1-6, and color each vertex that doesn't have a color, with the colors of $G_2$ that we didn't use in $G_1$ (there should be 4-5 of them).
25430
I want to prove this claim using contradiction:     Let $G$ be a simple graph with $n$ vertices. Prove by contradiction that $G$ has two vertices having the same degree (Consider the vertex of smallest degree and vertex of largest degree).    I think I know where to start. The vertex of the largest degree is $n-1$ in this graph and the smallest is 1. How can I use contradiction to prove the statement above? I studied the proof of this using pigeonhole but I wanna use contradiction this time.
73910
I have to prove that Connected graph is Eulerian Graph if and only if the number of edges in minimal cut is even.  Implication from left to right. Well if $G$ is Eulerian Graph then degree of each vertex must be even. It's oblivious if i try to disconnect graph by removing all edges connected to the vertex with minimal degree. But minimal cut can be done also by dividing graph into 2 connected graphs (each graph with more then one vertex) and i have no idea how to deal with it.  Implication from right to left - completly no idea.
46759
While trying to derive some formula, I encountered the following problem. Consider the set $C_n$ of all connected graphs on $n$ vertices. What is $$ \sum_{G \in C_n} (-1)^{|G|} ? $$ In other words, if we give a graph with an even number of edges a weight of $+1$, and a graph with an odd number of edges a weight of $-1$, what is the total weight of all connected graphs?  Here is an example: when $n=3$, any two edges form a connected graph, and the complete graph is also connected, so the value of the sum is $3 - 1 = 2$.  Surprisingly, the answer is $$ \sum_{G \in C_n} (-1)^{|G|} = (-1)^{n-1} (n-1)!. $$ This can be proved using the "exponential formula" (see e.g. the freely-available generatingfunctionology). The exponential generating function of all graphs, counted according to their parity, is $1+x$ (since for $n \geq 2$, the even and odd graphs cancel). Hence the exponential generating function for all connected graphs (counted according to their parity) is $$ \log (1+x) = \sum_{n \geq 1} (-1)^{n+1}\frac{x^n}{n} = \sum_{n \geq 1} (-1)^{n+1}(n-1)!\frac{x^n}{n!}. $$  My question is:     Is there an enumerative proof of the formula $$ \sum_{G \in C_n} (-1)^{|G|} = (-1)^{n-1} (n-1)! \quad ? $$
95292
Let $G$ be a simple graph on $n$ vertices. If $G$ has $k$ components and every component is complete prove that: $$|E| \le \frac{(n-k)(n-k+1)}{2}$$ I'm asking for advice.
61450
Can somebody give me an example of a graph on eight vertices that has a pair of pseudosimilar vertices? Or, is it not possible? If it is not possible, please do not give me a proof, as I would like to figure out how to prove it myself.     Definition: vertices $u$ and $v$ in a graph $X$ are similar if there is an automorphism of $X$ that maps $u$ to $v$. If $u$ and $v$ are similar, then the vertex-deleted subgraphs $X-u$ and $X-v$ are isomorphic. If $X-u$ and $X-v$ are isomorphic but $u$ and $v$ are not similar, we say that they are pseudosimilar.
101767
Use induction on $n$ to show that every graph on $n$ vertices has a bipartite subgraph with at least $|E(G)|/2$ edges.  I tried some examples and see that it works. But I am not sure how to formulate the problem using n to use induction.  Any tips or insights?
11787
Source is in , but it has no proof. Also, I am not completely sure what "unbalanced" means here. Non-equal number of even and uneven degrees?  What I am interested in, are there some universal properties of (connected) graphs that prevent hamiltonicity? Something to do with number of vertices versus edges, or average degrees or such? Something that is easy to demonstrate?  I will (hopefully) be using them as counterexamples of hamiltonian graphs in my thesis.
117224
suppose $n$ people are in a party and every two of them have exactly one common friends,prove that there is one who is friend to all.  I suppose there is no one who is friend to all,I want to show that the graph with this assumption is strongly regular graph and then show that two parameters $f,g=\frac{1}{2}(n-1 \pm \frac{(n-1)(\lambda - \mu)+2k}{\sqrt{(\lambda-\mu)^{2}+4(k-\mu)}})$ are not non negetive integers,my problem is when I suppose there is no one who is friend to all,I can't see that it is strongly regular graph.  of course this Idea was an help that was said in class,any other ideas will be great!  thanks.  something I must add is in this case every two adjacent or non-adjacent vertex has a common friends so $\lambda =\mu =1$ (if I am not wrong )now question is what is $k$? but it seems no matter what is $k$ ,because if $\lambda =\mu =1$ then $f=\frac{1}{2}n-\frac{1}{2}$ and it is not integer,I don't know what I am saying is right or wrong,please help me about this.