4

You can also have any number of cycles in the graph. If there is a $3$ cycle and a $77$ cycle she can only catch $1$ of the $3$ and $38$ of the $77$ for a total of $39$. If there are $3$ cycles of $3$ and one cycle of $71$, she can catch $38$. Each time a $3$ cycle is removed from an even cycle the count goes down by $1$ until we get to $25\ 3$ cycles and ...


4

Probably the easiest way to envisage the resulting graph is to visualize it in three dimensions as a polyhedron instead of a planar graph. Each added vertex is the top of a three-sided pyramid placed on an existing face (which face was added in the previous step, in fact). And the graph of such a polyhedron projects to a sphere which maps to the plane.


4

$$\sum\limits_{i\mid k_i=k} a_i,$$ also written $$\sum\limits_{i: k_i=k} a_i,$$ means to sum $a_i$ over indices $i$ such that $k_i=k$. To make it clearer that the formula is an average, I probably would have first defined $N_k = \{i \in N: k_i = k\}$ as the set of nodes with degree $k$ and then used the expression $$\langle \sigma \rangle_k = \frac{1}{|N_k|}\...


3

Try proving that the graph can be drawn by induction: given a suitably chosen drawing of the $n$-vertex $G$, it can be extended to the $(n+1)$-vertex $G$ by adding a vertex $v_{n+1}$ adjacent to $v_{n-2}, v_{n-1}, v_n$. For this to be possible, $v_{n-2}, v_{n-1}, v_n$ all have to lie on the same face of the $n$-vertex graph. Actually, since they are all ...


3

Let $e'$ be an edge with minimum weight in $T \cup T'$. Suppose for the moment that $e'$ is in $T'$. Then by assumption, $e'$ is not in $T$. It is well-known that in this case $T + e'$ contains a circuit $C$ and that for any edge $e \in C$, $T + e' - e$ is a spanning tree. The cost of this tree is $w(T) + w(e') - w(e) \leq w(T)$ (here we use the minimality ...


3

The technical term for what you're asking about is the query complexity of a graph property. Query complexity is exactly the number of entries of the adjacency matrix we must look at to determine if the graph has the property we want or not. The worst possible query complexity is $\binom n2 = \frac{n(n-1)}{2}$: the number of pairs of vertices to ask a query ...


3

Both you and the solution are wrong. Just saying that $\deg^-(c) \ne \deg^-(g)$ doesn't mean anything, because $c$ doesn't have to be paired with $g$. An isomorphism of these two directed graphs would be a function $$\phi : \{a, b, c, d\} \to \{e, f, g, h\}$$ that preserves directed edges. Checking that $\deg^-(c) \ne \deg^-(g)$ tells you that we cannot have ...


2

Suppose you had a cyclic sub-graph $G'$ of $G$. Then there would be some cycle in $G'$. This cycle would also be a cycle in $G$, contradicting the hypothesis that $G$ is acyclic.


2

Hint: if there were no elephants in England, then there would certainly not be any elephants in London, or Manchester, or any other English city. Generalize.


2

You'll have an easier time if you don't look at all the edges at a vertex at once. This is generally a good idea with the local lemma: many simple events are better than a few complicated ones. That's because we use the local lemma when the probability of avoiding all events is exponentially small. If you combine several events into one in such a case, you ...


2

These notes may provide a nice introductory beginning, with lots of figures and intuitive drawings (it may be more focussed on computational topology of graphs on surfaces, but the theory is introduced at every chapter in a very accessible way for a person not in the field): http://monge.univ-mlv.fr/~colinde/proj/16epit/eric-notes.pdf As stated in the ...


2

Already for $d=2$ you can have different possibilities based on what the connected components look like. If $2n=8$, for instance, the vertices can be arranged in a single $8$-cycle, or in two $4$-cycles. For larger $d$, you have even more flexibility. If you want a connected example, then we'll need $d \ge 3$, just as with ordinary $d$-regular graphs. But we ...


2

This is a path graph (Wikipedia, Wolfram). Wikipedia also calls it a linear graph but I see that much less frequently. It is denoted $P_n$, where $n$ is usually the number of vertices, but occasionally you see $P_n$ for the path graph with $n$ edges, instead.


1

Let $X$ be the random variable that counts the triangles in $G$. Then $$X = \sum_{i,j,k \in V(G)} \chi_{i,j,k}$$ where $$\mathbb{\chi}_{i,j,k} = \begin{cases}1, \; \text{if } \{i,j,k\} \text{ are pariwise connected} \\ 0, \; \text{otherwise} \end{cases}$$ From your question I am assuming that the graph is undirected and that the probability of each edge ...


1

You are almost there. Think of sending one unit of flow from the source to each of the $d$ destination nodes. You can express the whole system of constraints uniformly as one constraint per node: outflow minus inflow equals $d$ for the source node, $0$ for the intermediate nodes, and $-1$ for the destination nodes.


1

Here is a starting point that makes $O(n^2)$ calls to a max-flow subroutine: Let $\{v,w\}$ be an arbitrary pair of vertices in $G$. Iterate over pairs of vertices $\{x,y\}$ disjoint from $\{v,w\}$. (If you want both sides of your cut to be connected, then limit $\{v,w\}$ and $\{x,y\}$ to adjacent pairs of vertices.) For each case of $\{v,w\}$ and $\{x,y\}$, ...


1

Your answer are correct, for the proof we'll need few facts. I'll assume you know the handshaking lemma $\sum_V d^°(v) = 2|E|$ (the sum over all vertices of the degrees is two times the number of edges) ; and the characterization of trees with $n$ vertices as connected graphs with exactly $n-1$ edges there are no trees without degree one nodes to prove ...


1

It looks pretty good, I like the argument. But there are one or two stylistic things that you can do to improve the presentation of the statement and the proof. First, the statement itself is flawed in that there is a hidden hypothesis that should be made explicit: the tree is assumed to be finite. The statement is false if you allow for infinite trees (...


1

You were on the right track. From $$4x + 5y + 14 = 2x + 2y + 26$$ we get $$ 2x+3y=12 $$ It follows that $y$ is even and at most $4$, hence $$ (x,y)\in\bigl\{(0,4),\;(3,2),\;(6,0)\bigr\} $$ As we'll show, all $3$ of these potential pairs $(x,y)$ are, in fsct, possible. The image below shows an example with $(x,y)=(0,4)$. And the image below shows an ...


1

What you have done is correct so far. Now since $x\geq0$, we have $$6-\frac32y\geq0\implies y\leq4$$ Also, $x$ is an integer, so $y$ must be even. This gives the solutions $$y=4,\ x=0\\y=2,\ x=3\\y=0,\ x=6$$ These are the only possibilities. We must investigate whether any such tree actually exist. Notice that the subgraph induced by the non-terminal ...


1

Indeed, here is a way to construct (regular) graphs of size $O(n^{3/2})$ while controlling the (approximate) algebraic connectivity $a_c \in [0,2]$ with an error of order $1 \over n$. The rough idea is to start with a graph $G$ with small connectivity $\mu$ and to generate a family of product of graph $(G[H_k])_k$ whose connectivities are going to be $k \mu$...


1

First we find the probability that any set of 4 vertices is $K_4$. We say each potential edge can either be an edge in the graph (marked 1), or not (marked 0). We are given given $\mathbb P(edge=1) = p$ for all edges. Note for any set of 4 vertices, since there are $\binom{4}{2}$ edges. $P(K_4 \text{ given 4 vertices}) = P(\text{all edges between the 4 ...


1

Let $X_{ijkl}$ denote the indicator random variable that with (randomly) selected nodes $i,j,k,l$ there is a 4-clique ($K_4$) in the ER random graph $G(n,p)$, i.e., $ X_{ijkl} = \begin{cases} 1, & \text{if there is a } K_4 \text{ on } i,j,k,l \\ 0, & \text{otherwise} \end{cases} $ Then we have $E[X_{ijkl}]=P(X_{ijkl}=1)=p^6$ (since ...


1

You can complete the loop $a\to c\to b\to a$ by using the handshake lemma. For $c\to b$ you can argue that $T$ has $n-1$ edges, so the sum of the degrees of its vertices must be $2(n-1)=2n-2$. $T$ has $n-2$ vertices of degree at least $2$; if any of these vertices had degree greater than $2$, the sum of the degrees of the vertices of $T$ would be greater ...


1

Consider the graph $G_{m,n}$ with vertices $x_1,\dots,x_n$ and $y_1,\dots,y_{m}$ such that the edges are the ones of the form $\{x_i,x_j\}$ $\{x_i,y_1\}$ and $\{y_i,y_{i+1}\}$. We can calculate the average distance precisely but I'd rather not. Notice when $m$ is fixed and $n$ goes to infinity the proportion of pairs of vertices that are of the form $\{x_i,...


1

There's a couple notions of a "balanced graph" in general, but the handout isn't referring to any of them. It's somewhat related to the notion of balance used in balancing binary search trees, but that's actually optimizing a different quantity in a different context for a different purpose. Instead, the word "balancing" is being used for ...


1

As you observed, the problem is equivalent to the following: Write $80 = a_1 + \dots + a_k$ with each integer $a_k$ at least $3$. What are the possible values of $n = \sum_{i = 1}^k \lfloor \frac {a_i}2\rfloor$? The answer is that the possible values of $n$ are $27, 28, \dots, 40$. Firstly, we have $n \leq \sum_{i = 1}^k \frac{a_i}2 = 40$. Secondly, we ...


1

We can use the Pólya enumeration theorem to solve the problem for any particular $n,k,l$. I haven't been able to extract a formula for the general solution. Think of the sequences $x$ and $y$ as "coloring" the set $\{1,2,\dots,l\}$ by giving element $i$ the "color" $(x_i, y_i)$. If we give color $(x_i, y_i)$ weight $(x_i, y_i)$ as well, ...


1

As pointed out in the comments, it is easy to see that a Hamiltonian graph is $2$-connected. The Petersen graph furnishes an example of a $2$-connected graph that is not Hamiltonian. There is a Hamilton path starting at any vertex, as shown below. The red path is a Hamilton path starting at vertex D. So, if we delete vertex D, the graph is still ...


1

As you probably know, the question you ask is crucial in many random graph generation methods. Indeed, many of them start with a given (biased) graph in a class of interest and perform random small rearrangements of edges that mix the graph and are known to ultimately lead to a uniformly distributed random graph the given class. A typical example is edge ...


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