# Tagged Questions

34 views

### Hanoi Algorithm With Different Nodes

http://en.wikipedia.org/wiki/Tower_of_Hanoi I need help developing a Hanoi algorithm which follows the same rules as the standard game, however the nodes that are transversed is different. In this ...
29 views

### Minimum cut in a graph does not change when the weight of all edges is increased by one

Suppose we have a Graph $G$ in which weight of all edges is $> 1$ (positive). If we increase weight of all edges by one, why does the minimum cut $(S, T)$ of $G$ into two graphs remain the same? ...
34 views

### A probability of a monochromatic cycle on a randomly colored lattice graph.

Let $G$ be an undirected $6 \times 6$ lattice graph. The $36$ vertices of $G$ are each randomly colored with one of $5$ colors with equal probability. Such a coloring is called "successful" if and ...
30 views

### Prove that $G$ is Hamiltonian.

Let $G=(V,E)$ be a connected graph which is not a tree. Prove that if for every cycle $C$ of the graph G and for any $v \in V(G)- V(C)$ there are more than $\frac{|C|}{2}$ edges from $v$ to $V(C)$ ...
47 views

18 views

### Eccentricity of vertices in a graph when eccentricity of one vertex is given

I have a very basic doubt. If a vertex in any graph has the eccentricity two, then what can be concluded about eccentricities of other vertices in graph. Is the eccentricity of every vertex is less ...
23 views

### The “sides” of a k-regular bipartite graph are equal?

I was reviewing some lectures notes and noticed that in a proof of a theorem our lecturer stated that the "sides" of a k-regular bipartite graph are equal and that it is trivial to prove it. Anyway ...
42 views

### Graph Theory, with algorithms like kruskal and something more

The new government of the archipelago of Sealand has decided to join six islands by bridges to connect them directly. The cost of building a bridge depends on the distance between the islands. This ...
24 views

### Generators Trees in a Tree

My question is very short: How many spanning trees have a tree? Thanks in advance
54 views

### Stable Marriage - set of preferences such that every arrangement is stable?

This is a homework problem from the MIT OCW math for CS class, assignment 4, problem 5. Prove or disprove the following claim: for some n ≥ 3 (n boys and n girls, for a total of 2n people), there ...
47 views

### Does $K_{15,15}$ decompose into $K_{5,5}-C_{10}$ and $K_{5,5}-(C_6 \cup C_4)$ subgraphs?

Following on from this question: Q: Does $K_{15,15}$ decompose into $K_{5,5}-C_{10}$ and $K_{5,5}-(C_6 \cup C_4)$ subgraphs? or equivalently Q: Does there exist a $15 \times 15$ matrix ...
52 views

### Film Festival, with intersections graphs

I encourage you to read this problem. I have a doubt, have films 1 and 2 the same type? I read the problem and I think that films {1,3,5}, {2,4,6}, {3,4} and {5,6} are grouped, but not is the case ...
26 views

### Draw a graphic only passing one time

I would like to know when I can draw a graph, without lifting the pencil and passing once for each edge? What theory is behind that? Thanks for your time
45 views

### Making a Graph having edges

V is the set of those two-letter words built over {w, x, y, z} whose first letter is y or z. The graph G = (V, A) is defined so that two words of V determine an edge of A if they differ in exactly one ...
92 views

### Does $K_{12,12}$ decompose into $K_{4,4}-I$ subgraphs?

Q: Does the complete bipartite graph $K_{12,12}$ decompose into $K_{4,4}-I$ subgraphs, where $I$ is a $1$-factor (i.e., a perfect matching)? The obvious necessary conditions work: $K_{12,12}$ ...
44 views

### All $k$-regular subgraphs of $K_{n,n}$ have a perfect matching: a proof without Hall's Marriage Theorem?

There are several ways of describing this result: Theorem: For $k \in \{1,2,\ldots,n\}$, any $k$-regular subgraph of $K_{n,n}$ has a perfect matching (also known as a $1$-factor). I tend to ...
45 views

### Partition Graph Challenging Question

I want to find in which of the following Graph, the edges cannot partitioned to triangles? Km,n,r means 3-Partite Complete Graph with m, n, and r sections. a) K7 b) K12 c) K3,3,3 d) K5,5,5 i ...
18 views

### Planner Combination Problem on Graph

I ran into a Graph Problem. Suppose G is A Planner Graph with 100 Vertices such that if connect each two Non-adjacent vertices, the resulting graph would be non-planner. what is the number of edges ...
45 views

### Perfect Matching Combination Problem

We know: A perfect matching (a.k.a. 1-factor) is a matching which matches all vertices of the graph. if we remove edges of perfect matching of a 12-Complete Graph. how many triangle remain in this ...
36 views

### Convert adjacency matrix to graph

Is there any online service that can provide possible graphs (the simplest one) when I give a sequence of integers (node degrees) as input (or reject the input) -based on Erdős-Gallai formula? Thanks ...
19 views

### $k$ edge-disjoint $r$-arborescences in an acylic digraph

An $r$-arborescence of a digraph $D$ is a rooted spanning tree with root $r\in V(D)$ in which all the edges of $D$ are directed away from $r$. I would like to prove the following: I have thought ...
52 views

### Prove that a complement graph of a tree is either connected or it's a union of an isolated vertex and a full graph

I managed to prove the second part - that a tree that is one vertex with n-1 degree and all the rest are connected to it - the complement graph of such tree is an isolated vertex and the rest of the ...
14 views

### about the structure of components of tensor product if more than one bipartite graph is taken

I was reading about tensor product of graphs. We know that if we take tensor product of n graphs and want this product to be a connected graph then at most one graph should be bipartite. In the book ...
289 views

### Does every “balloon” (dragon, tadpole, canoe paddle) admit a graceful labeling?

8/18/14 Edit: If anyone has a copy of a related reference, then I would be happy to see it. For now, I am accepting the answer below and considering the question answered in the affirmative: Yes. ...
49 views

### Graphs without nontrivial automorphism

I'm trying to solve two problems about graph automorphisms. I want to construct a bipartite graph without a nontrivial automorphism. I want to find the smallest possible number of nodes for a graph ...
18 views

### Cactus construction

Is there someone who can explain me how can one construct the cactus of the minimum cuts of a graph? Or someone who can suggest me a book about cactus construction theory? Thank you in advance
27 views

### Min cuts of a graph with odd edge-connectivity

Let $G=(V,E,w)$ be a weighted graph with integer weights, odd edge-connectivity $k(G)$ and $|E|$ minimum cuts that are linearly independent (i.e. every edge is contained in a minimum cut). Is it true ...
26 views

### Show that if the diameter of an undirected graph is $d$ then there exists some vertex separator $S\subseteq V$ of size $|S| \leq { n\over d-1}$

Show that if the diameter of an undirected graph is $d$ then there is some set $S\subseteq V$ with $|S| \leq \frac{n}{d-1}$ such that removing the vertices in S from the graph would break it into ...
62 views

68 views

### Graph Theory Question On Exam Involving colorability of certain planar graph

I had a question on my exam and answered it using what I believe to be an Exhaustive Proof. The teacher marked it wrong, and while I understand there is a simple answer to the question, I would like ...
52 views

### Prove a 4-cycle exists in a graph with 100 vertices, each with degree of atleast 50

I hope I wrote the question well since it is my attempt at translating from the book. If it isnt clear enough, The question states that in every graph as described in the title a simple cycle of ...
43 views

### Proving breath first traversal on graphs [duplicate]

I am trying to proof the following algorithm to see if a there exists a path from u to v in a graph G = (V,E). ...
42 views

### Random looking Gray Codes or Hamiltonian Cycles on Hypercubes

Cyclic Gray codes come in many flavors and correspond 1-1 to Hamiltonian cycles on hypercubes. I would like to find a type that looks like a random walk on the hypercube. In a sense this is an ...
54 views

### Proofing a Reachable Node Algorithm for Graphs

I am trying to proof the following algorithm to see if a there exists a path from u to v in a graph G = (V,E). ...