Proove that a 3-regular bridgeless graph has perfect matching?
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.
26200
By simple graph I mean a graph with no loops or double edges.  If $C$ is a cycle and $e$ is an edge connecting two non adjacent nodes of $C$, then $e$ is called a chord.  I realize that one plan of attack is to choose any node, say $v_0$.  Then, since the degree of $v_0$ is $3$ there are $3$ other nodes connected to it.  Repeating this argument we will eventually have to reach a node that is connected by an edge to one of the previously used nodes.    I just don't see how this guarantees the existence of a chord.
72916
Can anyone show me why this graph is nonplanar (which Mathematica assures me to be the case) ?    The graph passes the simple test $e \leq 3v - 6$.  I have tried and failed to find subgraphs isomorphic to subdivisions of $K_{3,3}$ or $K_5$.  The subgraph arising from deleting the right-most vertex and its adjacent edges is also nonplanar. In that subgraph, since only 3 vertices have degree 4, I suppose we cannot find a subdivision of $K_5$, so there must be a subdivision of $K_{3,3}$, but I cannot see it.
123211
Is there a  squarefree ( with two prime divisors) betweem any two consecutive squares?
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.
120075
Problem: Show that every nontrivial connected graph $G$ has a closed spanning walk that contains every edge of $G$ exactly twice.  My Attempt: I've tried to consider two cases. First $G$ is Eulerian, then we have a Eulerian Circuit $C$, which could simply be traversed again. Next, suppose that $G$ is not  Eulerian. In this case, consider the  graph $G$ with additional edges $(u,v)$, where $u$ and $v$ are odd vertices. Then we have a graph which has essentially all vertices of even degree and so we obtain a Eulerian Circuit $C_1$. Now we delete all the edges thata re incident with odd vertices from this graph and thus we are left another subgraph $H$ which has all even vertices giving us another circuit $C_2.$ I claim that $C_1$ and $C_2$ cover all edges twice but I can't prove it. Please help.
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$.
4446
Let $G=(V,E)$ a graph. Prove that $G$ has no cycles if and only if $G$ has $n-m$ connected components where $n$ is the number of vertices of $G$ and $m$ is the number of edges of $G$.  The thing I did is that since $G$ has no cycles then $ \frac{m}{n} &lt;1$.  Can someone give me some hints-ideas?  Thank's in advance!
103193
Given a graph G is easy to see that we have a partition $V=V_1 \cup V_2$ so that  $$e(G[V_1])+e(G[V_2])\leq e(G)/2$$. How can we improve this result showing that we can choose $V_i$ such that $e(G[V_i])\leq e(G)/3$ for $i=1,2.$
115430
I am really stuck with the following graph problem:  Prove that for any natural $k\ge1$, there is a self-complementary graph of order $4k+1$ such that it is $2k$-regular.  I have a hint to use induction on k. Although I have found a method of constructing a $2k$-regular graph of order $4(k+1) + 1$ from the $4k+1$ graph, I cannot figure a way to prove it is self-complementary.   What I do for $k+1$ is that I split the k graph, let it be $G$, in 2 groups of $2k$ and $2k+1$ nodes, name them $A$ and $B$ respectively. Then I take a 4 node line graph, name it $H$, and connect its edge nodes to all the nodes of subgraph $B$, and the other 2 inner nodes to the nodes of subgraph $A$. This way, I have a $2k$-regular graph (the degree of every node is $2k+2$) and it is actually a union of 2 self-complementary graphs, $G$ and $H$. I guess I need to prove that this union is self-complementary.  I have spent hours trying to prove it, any help will be appreciated.
80524
Let $G$ be a connected planar graph with a planar embedding where every face boundary is a cycle of even length. Prove that $G$ is bipartite.  Any hints/tips will be greatly appreciated.
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.
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?
19561
I am trying to prove that the product of three consecutive positive integers is never a perfect power. Can anyone point to gaps in my proof and/or post an alternate solution?  Let the three positive consecutive integers be $n - 1$, $n$ and $n + 1$ and let $(n - 1)n(n + 1) = h^k, k \ge 2$. Note that $\gcd(n - 1, n) = 1$ and $(n, n + 1) = 1$ implies that $n$ itself must be a perfect power and of the form $z^k$ (which is apparent once we look at the canonical representation of $h^k$). That means $n^2 - 1$ must be a perfect power itself and of the form $a^k$. If $n$ is odd, $n = 2m + 1$ for some $m \in \mathbb{N}$ i. e. $(n - 1)(n + 1) = 2m(2m + 2) = 2^2m(m + 1) = a^k$. Using the fact that $(m, m + 1) = 1$, $m$ and $m + 1$ must be perfect powers themselves and so $k\leq 2$. Coupled with fact that $k &gt; 1$, we infer $k = 2$. So, $n^2 - 1 = a^2$ which implies $n$ is not a natural number. We are left with the case when $n$ is even. Let $n = 2t + 1$. $(n + 1, n - 1) = 1$ as both are of (by the Euclidean algorithm). That means $n - 1$ and $n + 1$ are perfect powers. So, let $(n - 1) = b^k$ and $(n + 1) = l^k$. So, $l^k - b^k = 2$ for natural $l$ and $p$ and $k&gt;1$. I will prove that the diophantine equation has no solutions. Consider the function $f(k) = l^k - b^k - 2$. $f'(k) = \frac{1}{l}e^{k\log l} - \frac{1}{b}e^{k\log b}&gt;0$ if and only if $e^{k(log\frac{l}{b})}&gt;\frac{l}{b}$. Taking logarithm again, we get an equivalent condition $(k - 1)\log\frac{l}{b}&gt;0$ which is true as $k&gt;1$ and $l&gt;b$ as log is a monotonically increasing function.  Is my proof correct? Please feel free to chip in with your own solutions!
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.
16314
Greetings Community! The above problem you see is a combinatorics problem I could not solve. :( This problem is from ZIO $2010$, P$1$.     Here is what I did: Observe that every graph can be divided into "sub-groups" which may help in solving. We first remove the empty set. Then the singleton set. Consider the bigger but smaller than the sub-parts example:    The singleton sets are $\{4,5,6\}$ which are at the least position in the graph.   The dual sets are $\{2,4\}, \{3,5\}, \{3,6\}$, the bottom - two portions in the graph. The triplet sets are $\{2,4,5\}, \{4,5,6\}$ which we may manually count but for the bigger graphs in the sub-part, this may prove to be difficult and this is where I am stuck.   Any help would be appreciated. Thanks.
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!