# Tag Info

## Hot answers tagged graph-theory

3

The following stronger result is known. Assume that the edges of the graph $G$ with $n$ vertices are drawn in mutually independently with probability $\frac{c\ln n}{n}$. Then, for a sufficiently large $c$, the probability that $G$ contains a Hamiltonian circuit tends to $1$ as $n \to \infty$. This is Theorem 2 from this old paper by Pósa, available online ...

2

This is often called the Manhattan distance between two points, because cars in Manhattan can only drive on vertical and horizontal roads. The Manhattan distance between $(x_1,y_1)$ and $(x_2,y_2)$ is $|x_1-x_2|+|y_1-y_2|$.

2

A leaf of T has degree $1$, and there is a vertex with degree $2$. So, the complement of T has a vertex with degree $n-2$ and a vertex with degree $n-3$, so the complement of T cannot have vertices which degrees are all even.

2

It is not a priori valid to assume that a tree on $k+1$ vertices is obtained by adding an edge to a $k$-vertex tree. Instead, you should start from an arbitrary* $(k+1)$-vertex tree and then e.g. investigate what happens upon removing an edge. * I'm not sure if "arbitrary" counts as a pun in this context (arbor is latin for tree)

2

Remove a leaf of a spanning tree.

1

Choose two vertices $u,v$ which maximize the distance $\operatorname d(u,v)$. If $w$ is any other vertex of the graph, the shortest path from $v$ to $w$ does not go though $u$ (else $v$ and $w$ would be farther apart than $v$ and $u$), so deleting $u$ leaves a connected graph.

1

Start with the empty graph (no edges) on $p$ vertices; so $q=0$, $c=p$, $q-p+c=0$. Now draw the edges one by one. Each time you add an edge, either the new edge joins vertices in two different components, so $q$ increases by one, $c$ decreases by one, $q-p+c$ is unchanged; or else the new edge joins two vertices in the same component, $c$ is unchanged, $q$ ...

1

It's an unsolved problem whether graph isomorphism can be decided in polynomial time. That's irrelevant here, because "polynomial time" is about large problems and asymptotics, and your problem is about a fixed pair of very small graphs. It took me about a minute to find an isomorphism by trial. First, I looked at the big pentagon on the left, and labeled ...

1

Adding an answer following @Irvan's comment above: The bin packing problem ("Given $n$ items of sizes $d_1,...d_n$ and $m$ bins with capacity $c_1,...,c_m$ store all the items using the smallest number of bins.") could be reduced to this problem in polynomial time. If we had the algorithms in the question, we could map the items to books and bins to bags, ...

1

Showing two graphs are isomorphic/non-isomorphic involve showing that the two graphs are structurally the same/different. The names of the vertices are not structural properties so we have to take care that names are not the crucial part of the proof. To show two graphs are non-isomorphic, we must consider all possible bijective mappings between the two ...

1

If you can make $G-e$ disconnected by removing $k=\kappa(G-e)$ vertices, then removing the same $k$ vertices from $G$ either makes $G$ disconnected as well or turns $e$ into a bridge and then removing one of the end points of $e$ disconnects $G$; hence $\kappa(G)\le k+1$.

1

For simplicity assume that each entry of the matrix is either $1$ or $0$. Define a bipartite graph $G=(X,Y)$ where $X=\{r_1,\ldots,r_m\}$ and $Y=\{c_1,\ldots,c_n\}$. Join $r_i$ with $c_j$ by an edge of and only if the $i,j$-th entry of the marix is $1$. Note that $\deg(r_i)$ is same as the sum of the entries in the $i$-th row. Similarly, $\deg(c_j)$ is ...

1

@Raoul , @Diane Vanderwaif http://i.stack.imgur.com/lOVPS.png I think the graph is two edge connected because we can seperate the vertex in the top from the sequare in the bottom by removing two edge (We will get a vertex with degree zero and C4)

1

Hint: Prove that $\kappa(H)=\kappa(G)+1$. Prove that $\alpha(H)=\alpha(G)$. Apply theorem 3.15. Figure out how a Hamiltonian cycle in $H$ translates to a Hamiltonian path in $G$.

1

HINT: Think of a triangle $ABC$ with $AB=3$, $BC=4$, $AC=5$. The minimum spanning tree contains the edges $AB$, $BC$ and $AB+ BC > AC$.

1

Yes. Consider the two vertices which have maximum distance in the spanning tree. It is not hard to see that the two vertices can be connected with an edge with weight low enough to be less that the weight of the path, but high enough to be excluded in the formation of tree. Consider the graph as below, where W(m, n) is the weight of the edge connecting ...

1

I don't know enough about how this stuff works for directed graphs (can you just stick random orientations on the edges and then apply the result for directed graphs? or maybe double up each edge so that you have one going each way?), so the below (which approximately follows Diestel) might not be the quickest approach. Let $G$ be a connected graph with $n$ ...

1

Try to draw graphs which satisfy conditions I and II. If you are successful, you can rule out that case, and if not, this may help you realize why that case is impossible.

1

It’s not hard to construct a graph with $2$ vertices of degree $2$ and $5$ of degree $2$; you should try to do so. That suggests that you should try to show that (I) is impossible. However, the problem is defective, because (I) is actually also possible. Let the vertices be $x,y,z,a,b,c$, and $d$, and let the edges be $xy,yz,xa,za,xb,zb,xc,yc,yd$, and $zd$. ...

1

There should be always a fair driving schedule since you can model this problem as a flow network. The source is connected with all persons and the capacity of an edge from the source to a person $p_j$ is $\lceil\delta_j\rceil$. The next step is to connect every person with each of his working days. The capacity of each of this edges is $1$. The last step is ...

1

The following is a partial answer, perhaps useful in pointing out a subtlety in how graphs are to be counted for the purpose of giving an asymmetric proportion. Edit: It turns out that much the same point is made (more forcefully) by Brendan McKay's accepted answer to this MathOverflow Question about density of asymmetric graphs. According to Babai's ...

1

For any simple polygon, the sum of the exterior angles (i.e. the supplements of of the interior angles) equals $360^\circ$. And for a convex polygon, the exterior angles are all nonnegative. Hence at most 3 of the exterior angles can exceed $90^\circ$, i.e. at most three interior angle scan be acute.

1

Here is the theorem that manuellafond pointed to. Here, $\kappa (G)$ is the connectivity of $G$ and $\alpha(G)$ is the independence number. Theorem (Chvatal-Erdos): If $G$ has at least three vertices and if $\kappa (G)\geq \alpha(G)$, then $G$ is Hamiltonian. Proof: Let $C=(v_1,v_2,\ldots,v_k)$ be a cycle of maximum length in $G$ where $v_i$ is ...

1

Note that the result says that we can partition $G$ into $V_1,V_2$ in such a way that all vertices in $G[V_1]$ and $G[V_2]$ have even degree. A proof of this is given in Combinatiorial Problems and Exercises (Lovász): If all the vertices have even degree then we're done. Assume that $v$ is a vertex of odd degree with neighbours $N$. Let $G'$ be the graph ...

1

In this case it's simple: the sum of the grades must be even for the Handshaking Lemma. In general, there's a rule for deciding if a sequence of numbers is a grafic sequence, that is, there exists a graph whit that sequence as the degree sequence of his nodes: general rule

1

In general this is fairly interesting (although solved). The Erdős–Gallai theorem gives necessary and sufficient conditions for there to exist a graph whose vertices have specified degrees, and the Havel-Hakimi algorithm is an algorithm for efficiently determining whether the conditions are satisfied. In your case it's simpler, because one of the ...

Only top voted, non community-wiki answers of a minimum length are eligible