Tag Info

New answers tagged

0

Looks like there are 4 maximal matchings:{3,1}, {3,4}, {3,5}, {2}. They're matchings, since they do not share any vertices, and they're maximal since by adding any additional edge (to any of those three) necessitates the existence of a shared vertex, thereby rendering them as non-matchings. It may help to see it (more immediadely/clearly) if you label the ...


0

You can express the problem using recursion. So, to count the number of paths from $u$ to $v$ that don't go through any vertex in $S$: If $u = v$ then return $1$, else if $u \in S$, return $0$, else: let $C$ be the set of neighbours of $u$, and return $\sum_{c \in C} ($the number of paths from $c$ to $v$ that don't go through $S \cup \{u\})$. The answer to ...


1

Let $G$ be a finite simple graph. What I do below also works for directed graphs, replacing everywhere the word "walk" by "weak walk." Definition: For vertices $x,y$ in $G$, say $x\sim y$ precisely when there is a walk in $G$ from $x$ to $y$. Proposition: The relation $\sim$ defined above is an equivalence relation. Proof: The details are easy to work ...


1

One standard way to categorize graphs is as connected or disconnected. A disconnected graph can be decomposed into a series of graphs that are not connected to each other. I would refer to one of those as a component. A subgraph on the other hand is a subset of vertices of the original graph along with a subset of edges.


0

A component is 'closed' in the sense that if you have some vertex $v$ in a component, then any vertex which can be reached by a walk from $v$ is contained in the component. A subgraph does not have this restriction (it's just a subset of vertices and edges from the entire graph).


1

For generalized Petersen graphs it's easy to construct required automorphisms - there are obvious rotational symmetries taking any outer vertex to any other outer vertex, and any inner vertex to any other inner vertex; and there is the "turning inside out" symmetry which takes the inner "star" to the outer regular polygon; compositions of these show that the ...


0

I presume by "ratio" you mean something like $\frac{|N(A) \cap N(C)|}{|N(A)| + |N(C)|}$ where $N(X)$ is the neighbor set of $X$. This is an example of "collaborative filtering," and it's a technique applied in machine learning. You can read about it here or here, for example. I presume you are describing a situation of the following form: if $A$ and $C$ ...


1

Revised answer after your edit: I'm not sure where you're getting the numerator ${n-1 \choose (n-1)/2-k}$ in your expression for $P[D_v]$. It looks like you're trying to count the number of ways to choose the $(n-1)/2 - k$ remaining out-neighbors for $v$, since we're assuming that $v$ is adjacent to each of the $k$ vertices in $S$. But you're making this ...


0

I think that you removed one-too-many when you were accounting for overcounting. Specifically you removed the copy of $C_3$ made up of exactly the edges $xy$, $yz$, and $xz$. I thought about the problem by classifying the copies of $C_3$ by how many of edges in $\{xy, yz, xz\}$ it contains. There is only $1$ copy of $C_3$ that contains all three of ...


0

In graph theory and more specifically in rooted plane trees there is a fundamental sentence: The number of rooted plane trees with n nodes equals to n-th Catalan number, that is |Tn| = Cn. I hope to have helped you.


2

First, the graph must be undirected (if it's directed and there exists an edge from $a$ to $b$ but not from $b$ to $a$, then if $X_1 = a$ and $X_2 = b$, it is impossible to have $X_{n-1} = b$ and $X_n = a$. Let $d(x)$ be the out degree of node $x$: $$P(X_i = x_1, \ldots, X_n = x_n | X_0 = x_0) = \prod_{i \in [0, n)} d(x_i)^{-1}$$ $$P(X_i = x_{n-1}, ...


1

On 1: Suppose a node is on depth $i$ from the root (the root is on depth $0$, its direct children is of depth $1$, etc). What is the probability of this node to still be connected to the root? It is equal to the probability that none of the $i$ edges between it and the root is removed, i.e. $$2^{-i}$$ For a node of depth $i$ from the root, define $X_i$ to ...


2

On 2) The probability that a sequence of length $k$ is monotone is $\left(k+1\right)2^{-k}$. This because there are exactly $k+1$ distinct patterns that will be labeled as monotone, and each pattern has a probability of $2^{-k}$ to occur. A sequence of length $n$ has $\binom{n}{k}$ subsequences of length $k$. Give each a number $r\in\left\{ ...


0

Yet another proof. You will always going to have a vertex with degree odd or even. Erase an edge whenever a vertex has degree odd, taking care of no erasing an edge incident to a vertex of degree 2. The remaining graph has a closed Euler walk, thus having at least one cycle.


1

Yes, $G$ can have multiple components. Assuming $\Delta(G)$ does indeed represent the maximum degree (or even if it somehow means average degree), then consider the disjoint union of a $K_{n-2}$ with a $K_2$. The average degree will be $(n-2)(n-3)+2 > \frac{n}{2}$ and the maximum degree will be $n-3>\frac{n}{2}$ for large enough $n$.


0

If $i \neq j$ is guaranteed then your calculation looks correct. However maybe you have to assume that $i,j$ are chosen uniformly randomly so $i = j$ is a possibility, with probability $1/n$?


0

[This partially answer the question, because this solution doesn't use the revolving door ordering algorithm, which is stated over literature as the best (i.e., computationally efficient) algorithm to the task] I didn't understand really well the revolving door ordering algorithm so I didn't implement it, of course I could just code the algorithm without ...


0

hints can you write down definitions of cut vertex and cut edge and think what happens in a graph without cut edges? think of a graph that looks like an $\infty$ sign, what happens if you remove the vertex in the middle?


0

You need to 'Show' it. That may be a lesser requirement than a formal proof. Certainly for only 3 points on your exam. Then it is probably sufficient to tell that you will at least need a tree of depth $L$, but you also don't need more than $L$. Where $L$ is the length of the shortest path. You just rearrange the vertices at level $l$ in $1..L$ as the ...


2

Your base case holds. Suppose we have a cycle-free, connected graph $G$ with $n$ vertices. and $n-1$ edges. Because $G$ is cycle-free, there is a vertex with degree $1$. Delete this vertex. We are left with a connected graph $G'$ with $n-1$ vertices and $n-2$ edges, which is a tree by induction. Reattaching the former pendant vertex does not introduce a ...


3

There are (at least) two kinds of neighborhoods commonly appearing in statements about graphs. The closed neighborhood of a vertex $v$ is the set of all vertices adjacent to $v$ together with $v$ itself. The open neighborhood of $v$ is the set of all vertices adjacent to $v$ excluding $v$ itself. These are sometimes denoted by $\overline{N(v)}$ and $N(v)$, ...


1

Let $(v_0,\ldots,v_{k})$ be a path of length $k<10$. Now, how many neighbours does $v_k$ have? Conclude that you can extend your path to a longer path.


0

This is a reduction from undirected Hamilton Cycle to undirected Hamilton Path. It takes a graph $G$ and returns a graph $f(G)$ such that $G$ has a Hamilton Cycle iff $f(G)$ has a Hamilton Path. Given a graph $G = (V,E)$ we construct a graph $f(G)$ as follows. Let $v \in V$ be a vertex of G, and let $v',s,t \notin V$. We want to make $v'$ a "copy" of $v$, ...


1

You can just apply your previous question to the inequality $\kappa(G)\leq \lambda(G)\leq \delta(G)$ which holds for any graph $G$.


1

You ask "Did I go wrong somewhere...?" I'm having trouble following at a number of points in your post, which may be a sign that something is wrong, or at least of some things that ought to be clarified. You say The number of returning paths on 3-regular graphs of length $r$ without backtracking may be written as $2^{-r/2}p_r(x/\sqrt{2})$ which is a ...


1

There is not really a need to quote that inequality in this case: you can directly show that both values are $n-1$. Certainly $\delta(K_n)$ is $n-1$ as you know, and now just apply the definition of $\kappa$ to see that $\kappa(K_n)=n-1$: Since $K_n$ contains at least (well, exactly) $(n-1)+1$ vertices and there is no set of $(n-1)-1$ vertices whose removal ...


0

This idea is not new. You may take a look at the following paper, for example http://epubs.siam.org/doi/abs/10.1137/080734935 . There is also something you can do for chaotic system if you use Ulam method to approximate the transfer operator of the system. Then you can measure the force of chaoticity of the system in a sense, and approximate its invariant ...


1

A subgraph $K_r$ of $K_n$ is completely determined by the set of $r$ vertices chosen, so there are indeed $\binom{n}r$ of them. I’m assuming that $P_r$ is the path graph on $r$ vertices. Every sequence of $r$ of the vertices of $K_n$ determines a unique directed path, and there are $\frac{n!}{(n-r)!}$ such sequences, so there are $\frac{n!}{(n-r)!}$ ...


1

There was just a question on Hall's theorem. Hall's theorem gives a necessary and sufficient condition for a relation from $A$ to $B$ to restrict to an injective function from $A$ to $B$. The condition is that for all $A' \subset A$, $|n(A')| \geq |A'|$ where $n(A')$ is the set of neighbours of $A'$ in $B$. Naively this would take $2^n$ time to check. This ...


1

You need to "clone" each of the winners. Now $|A|=2n$. Each winner $W$ has two clones $W_1$ and $W_2$. Now the vertices of the bipartite graph are all the clones on one side, and all the prizes on the other. Each clone has an edge to all the prizes that the winner wants. A matching covering all the clones will assign each clone exactly one prize, and ...


0

Let $R \subset A \times B$ be our relation. Compute the two cardinalities $$n=\{ a \in A : \exists b \in B : a R b\}$$ $$m=\{ b \in B : \exists a \in A : a R b\}$$ If these two cardinalities are equal to the cardinality of $A$, then $R$ can be restricted to an injective function, otherwise no. EDIT: This is only a necessary condition. See comments below ...


0

See here for a pretty good Wikipedia page Let $\mathcal{V}_n = \{V_{\pm,\pm,\ldots,\pm} = (\pm 1, \pm 1, \ldots, \pm 1)\}$ with $n$ many subscripts denotes the vertex set of $Q_n$, and let $\mathcal{E}_n = \{(V_\alpha, V_\beta)\}$ be its set of (undirected!) edges. Don't worry about the details of $\mathcal{E}_n$ just yet. We can very easily construct the ...


0

In order for a graph to contain an Eulerian path or circuit there must be zero or two nodes of odd valence. This graphs has more than two, therefore it cannot contain any Eulerian paths or circuits.


0

The reason is simple, if you look closely you'll see no verticies lines has been broken nor any verticies been removed, hence they ahve just moved around and are therefore the same, isomorphic.


1

Think of this as pushing the vertices $f,b,d$ inside of the triangle $a,e,c$. There are plenty of four cycles in the second graph as well one is $a \rightarrow b \rightarrow d \rightarrow e \rightarrow a$


1

I built the game in Mathematica using the rules I think you're trying to accomplish. Here is the code if you have Mathematica: $\hspace{3cm}$ bound = {{2, -1}, {2, 5}, {1, 0}, {3, 0}, {0, 1}, {4, 1}, {0, 2}, {4, 2}, {-1, 3}, {5, 3}, {-1, 4}, {5, 4}, {-1, 5}, {5, 5}, {0, 6}, {1, 6}, {3, 6}, {4, 6}} DynamicModule[{pos1 = {x1, y1} = {2, 2}, pos2 = ...


0

Indeed, the faulty assumption seems to be that "Euler's Formula is used to test whether a graph is planar." As you've pointed out, this line of reasoning doesn't really make sense - mostly, without a planar drawing, the number $f$ isn't well defined! This is exactly what trouble you ran into ($f$ not being well defined) when looking at different drawings of ...


1

You can say $G$ is disconnected. Suppose $G$ is connected. Since $G$ is connected it contains at least on spanning tree. Lets call this tree $T$. Now consider the edge $uv$. Take $T$ and assume it does not contain edge $uv$ (if it does we are done), since $T$ is a tree it contains a unique path between $u$ and $v$ label this path $ux_1\dots x_nv$ Remove the ...


4

Consider a spanning tree. Then adding your edge $e$ creates a cycle. Removing any other edge of this cycle creates a spanning tree containg $e$. Hence there is no other edge in the cycle, which means that the edge must be a loop.


0

The notation {2, 2, 2, 4, 5, 5} is the degree sequence of the graph and is often written in descending order like : [5, 5, 4, 2, 2, 2]. The Havel-Hakimi theorem gives an easy way to check if a sequence is 'graphical' (makes a graph). Conceptually, you take the highest degree d in the sequence and take one from the d next highest degrees. This is done ...


2

No matter how you play the game if you start with a stack of $n$ piles your score is always going to be $\frac{n(n-1)}{2}$. When we play the game for every step we add $a\cdot b$ where $a$ and $b$ are the sizes of the stacks we obtain after dividing a stack of size $a+b$. $a\cdot b$ is the same as going block by block and for each block adding the number of ...


1

I think you are misunderstanding the definition of planar graphs. It means that you can draw it to the plane without it's edges crossing each other. $K_4$ is for sure a planar graph, for example: About Euler's formula: You can only use that if you drew a graph to a plane without it's edges crossed. In that case, you can use it to determine whether or not it ...


1

An oriented graph is an undirected graph with orientation. Think of it this way, every oriented graph is a directed graph, but not viceversa. Every oriented graph can be obtained by taking a simple undirected graph and assigning a direction to every edge. This is not true for every directed graph. Basically directed graphs can have an arrow going from $A$ ...


1

A graph $G$ that is factorizable ($1$-factorizable) must have an even number of vertices. This is because for it to be factorizable, in particular it must contain at least one factor ($1$-factor, also known as matching). So it must contain a generating subgraph that is regular of degree $1$. If $G$ had an odd number of vertices this would be impossible ...


0

If we take a connected graph and add a vertex to it (along with at least on edge adjacent to that vertex) then the radius increases by at most $1$. This tells us if we remove a vertex from a graph the radius decreases by at most $1$. Take a graph $G$ and consider the graph with the least number of vertices that has radius $r$. Call it $H$, if we remove a ...


1

Note that in a graph of maximum degree $d$, for a fixed vertex $v$ there are at most $d$ vertexes at distance $1$ from $v$, at most $d(d-1)$ vertexes at distance $2$ from $v$, at most $d(d-1)^2$ vertexes at distance $3$ from $v$, and so on. Take $v$ a vertex that is a "center" so has distance at most $3$ to each other vertex and do the calculation. ...


0

Let $k$ be the edge-connectivity of $G$, so $|S|=k$, and $\delta(G)\geq k$. $S$ is a minimal disconnecting set of edges, so $G-S$ has exactly two components(!), call them $X$ and $Y$. Let $A$ be the vertices of $X$ that are endpoints of an edge of $S$. Let $B$ be the vertices of $Y$ that are endpoints of an edge of $S$. We claim that $X-A$ and $Y-B$ cannot ...


2

The spine of a tree $T$ is the tree we obtain by simultaneously removing all leaves of $T$. Let $T$ be a spanning tree of $G$. Start walking anywhere and visit every leaf exactly once, returning to a vertex that belongs to the spine of $T$. Now remove all leaves, continue your walk and visit every leaf of the new tree that has been visited an even number of ...


2

It is quite common to just say "graph" and implicitly assume that the graph has no multiple edges. This usage goes together with the word "multigraph" to describe a graph that may have multiple edges. The terminology "simple graph" is also available to specify this, but is more often used in context where it is already established that multiple edges are a ...



Top 50 recent answers are included