Jernej
Reputation
1,966
Top tag
Next privilege 2,000 Rep.
 Mar6 asked Bounding probability of some events with bounded depdendence Feb26 comment Probabilistic method: vertex disjoint cycles in digraphs @ManuelLafond Interesting. Where did you find this proof? I think one can fix it by using the asymmetric LLL perhaps at the expense of a worse constant. Feb26 comment Probabilistic method: vertex disjoint cycles in digraphs @ManuelLafond I've spoken with the author and he confirmed its a mistake. One would somehow have to include this event C as well. Feb25 asked Probabilistic method: vertex disjoint cycles in digraphs Feb19 comment Does there exists a $k$-critical graph having connectivity $2$ for every $k\geq 3$? Note that by definition, $K_k$ is $2$-connected for any $k > 2.$ Feb18 comment For every r exists large enough n such that any graph… Which propositions are you allowed to use then? Feb17 comment Finding the spanning subgraphs of a complete bipartite graph @chowching I suggest that for a start you look at Harary's and Palmer's book called "graphical enumeration" Feb17 comment Finding the spanning subgraphs of a complete bipartite graph @chowching You can but the formula will most likely require using computer computations. Feb17 comment Finding the spanning subgraphs of a complete bipartite graph @chowching You should be more specific about what you're looking for. Note that in general there is no closed formula for the number of bipartite graphs with bipartitions of cardinality n and m. Feb17 comment min degree at least $n+1/2$, every edge on Hamilton cycle I guess you must visualize this thing. Just to be sure $G/e$ denotes the graph obtained by contracting the edge $e$? Feb17 comment min degree at least $n+1/2$, every edge on Hamilton cycle That should be enough. If you extend the hamiltonian cycle in $G'$ to a cycle of $G$ it uses the edge $e$ Feb17 answered Finding the spanning subgraphs of a complete bipartite graph Feb15 revised Prove that for every connected graph $G$ of order $n$ and diameter $d$ , $\chi(G)\leq n-d+1$ deleted 69 characters in body Feb15 comment Prove that for every connected graph $G$ of order $n$ and diameter $d$ , $\chi(G)\leq n-d+1$ @ctlaltdefeat Good point. Edited my answer. Feb10 comment Isomorphic but not equivalent actions of a group G @RobArthan Some lectures notes from a class I have. Feb10 asked Isomorphic but not equivalent actions of a group G Feb10 comment Graph Theory Function (Thomassen) Btw doesn't the claim follows quickly from 1 and 2? By lemma $2$ you get a minor with large average degree provided that your graph has large girth. By picking a suitably large girth , the min degree is then large enough so that the average degree satisfies the conditions of lemma 1 giving you the desired complete graph as a minor. Where exactly do you get stuck? Feb10 comment Graph Theory Function (Thomassen) @Lindsey I have a recollection of seeing this thing proven in Diestel's book. Feb8 answered Prove that for every connected graph $G$ of order $n$ and diameter $d$ , $\chi(G)\leq n-d+1$ Feb7 comment A question about the interlacing of symmetric matrices (graph interlacing) Hm.. that makes sense, thanks!