New answers tagged

0

Suppose $G$ is a $2$-edge-connected graph on $n$ vertices. Let $T$ be a spanning tree of $G$ with edge set $E(T)=\{e_1,\dots,e_{n-1}\}.$ For each $i\in\{1,\dots,n-1\},$ since $G-e_i$ is connected, we can choose a spanning tree $T_i$ such that $T-e_i\subset T_i\subseteq G-e_i.$ The spanning trees $T,T_1,\dots,T_{n-1}$ are distinct because $E(T)\setminus ...


0

The name of the operations containt inesrtion of vertices and removal/insertion of edges as written in the picture. Other way to see this is to consider graph theory in terms of linear algebra. So the path matrix $P_{in}$ where $in$ is the root is {{1, out}, {2,out}, {3,out}, {4,out}} while the reduced path matrx $P_{in}^{-1}$ is {{1}, {2}, {3}, {4}} with ...


0

You can do this by adding an edge from the sink to the source, with cost $-1$ and an infinite capacity. The other edges have $0$ costs. The minimum cost flow will try to send as many units of flows from the sink to the source, as it is the only edge with a negative cost. This is precisely what you need for a maximum flow problem.


3

Take your vertices to be the mathematicians, put edges bewteen two mathematicians in conflict, and choose one color per hotel. Then the question becomes : can you color this graph such that adjacent vertices are always of different colors ?


1

You can define a bijection between $n$-tuples on $\{0,1\}$ and subsets of an $n$-element set. The basic idea is that the tuple is the characteristic function of the subset, or in other words, we include an element in the subset if the corresponding position in the tuple is non-zero. Define $\phi: \{0,1\}^n \to \mathcal{P}(\{1,2,\ldots,n\})$ as ...


0

The key terms seems to contain cycle space (linear algebra), orthogonal complement (linear algebra), cut space (linear algebra) -- in order to understand concepts in graph theory. The jargon seems to vary over different domains. Definitions Cycle and cycle spaces seem to have distinct definitions, more here: "The term cycle may also ...


0

You're calculating as if the three events whose probabilities you're multiplying were independent, but they're far from independent. The probability for a given edge to exist and be isolated is $p(1-p)^{2(n-2)}$, where the factor of $p$ is for the edge to exist and the $2(n-2)$ factors of $1-p$ are for the remaining $2(n-2)$ edges of the endpoints of the ...


1

As far as I am aware, the junction tree algorithm can be used as an approximation even in the case that the graphical model is not acyclic, since it creates a factor graph representation of the original model on which belief propagation can be performed (even though the results are only exact if the original model was itself acyclic). This is called ...


4

You are looking for an $(n,d,\lambda, \lambda)$ strongly regular graph. The normal labelling of the parameters are $(v,k, \lambda, \mu)$, so you are considering the special case where $\lambda = \mu$. There are lots of necessary conditions for the existence of a strongly regular graph. In particular, there are formulas to give the eigenvalues (there are ...


1

Hint: Assume we have Fano1 and Fano2 given, and pick and fix any three noncollinear points in both, call them e.g. $O_1,X_1,Y_1$ and $O_2,X_2,Y_2$. Try to express the lines and the further points in terms of 'intersections' and 'lines on two points'.


1

Let $d$ be the diameter of $G$, $n$ the number of vertices of $G$. Let $v,w$ be two vertices realizing the diameter of $G$, i.e. there is a shortest $v,w$-path $v=v_0,v_1,\ldots,v_d=w$ (call it $P$) of length $d$. Note that $P$ has $d+1$ vertices. For the lower bound, note that one vertex can dominate at most three vertices of $P$ (or we find a shorter ...


1

You're right that $E[Y]=E[X]$, but I don't quite follow how you calculated $E[Y]$. I'd phrase the probabilistic argument as follows: Your weighted selection of a person can be expressed as uniformly picking a friendship and then uniformly picking one of its two friends. If we now uniformly select a friend of this person, we're uniformly selecting a ...


1

Take $3$ pentagons. Add an edge between a given vertex and all other vertices belonging to the two other pentagons. To color a pentagon, you need $3$ colors, so to color this graph, you need exactly $9$ colors, but the clique number equals $6$.


0

Without Induction: Suppose it had less than two leaves. If it has zero, then we start at an arbitrary source node. All nodes have degree $\geq 2$, hence we can take an edge to some node, take a different edge to some other node, and so forth. By pigeonhole principle, we must eventually run into a node we've already seen, hence there is a cycle. If it has ...


0

Here is a simple proof using "complete induction" (aka "strong induction" aka "course of values induction"). Consider any integer $k\ge2.$ Assuming that every tree with at least two but fewer than $k$ vertices has at least two leaves, we prove that every tree with $k$ vertices has at least two leaves. Let $T$ be a tree with $k$ vertices. Choose a vertex $v$ ...


0

I think your base case and induction assumption are fine. For $P(k+1)$, we can in fact ignore all the vertex additions that result in a cycle since tree do not contain cycles. So let us only consider the possible vertex additions that result in trees. Case 1: Since $P(k)$ has at least 2 leaves, adjoining the new vertex to a node that is not a leaf would ...


3

I would first prove that every tree has at least one leaf. Added: You have in fact tacitly assumed this in your first bullet point, when you say that every tree on $k+1$ vertices is obtained by adding a vertex to a tree with $k$ vertices. This requires that you be able to remove a vertex from a tree on $k+1$ vertices and still have a tree. This cannot be ...


0

This is a good start, but you should more explicitly use the induction hypothesis. Also be sure to treat both possibilities: what if the new node is connected to a node which used to be a leaf? Check that we still have at least 2 leaves.


-1

Since I am not very mathematically inclined, I can only do computer simulation to first try simple paths, then slowly try more sophisticated paths. My computer simulation will just pick $2$ random positions for the walls if they are present based on their probabilities. There are $5$ main cases to handle for this problem... $1$) no wall, $2$) small wall ...


2

jwsiegel has already provided both an asymptotic answer to the original question, and a link to a closed-form solution. I will address the Juan's question in the comments on jwsiegel's answer and Jens's follow-up question in the original post. In answer to Juan's question, "For even n, this is better, but does this work if n is odd?": Nothing in jwsiegel's ...


2

For a 4-regular graph with $v$ vertices and $e$ edges, the handshaking lemma tells us that $v=2e$. In particular $v$ is even. We have the trivial solution of the empty graph ($v=e=0$), which is vacuously planar and 4-regular. If that is considered cheating, let's exclude it and assume $v\ge 1$. We also could have $v=2$ and $v=4$, but only if we allow ...


1

Remember that the shortest path is between two points, while the minimum spanning tree is the tree that spans the entire graph, and not just two points. If you consider a triangle with side lengths of 1, can you see the MSP and the minimum path between all pairs of vertices in your head? do they differ for one pair of vertices?


0

It's not exactly clear what you are asking. Are you trying to write $K_{1,3}, C_5,$ and/or $K_{1,3} + C_5$ as the Cartesian product of two graphs? You've shown that it can be done for $K_{1,3}$ but it can be shown that you can't do it for $C_5$ or $K_{1,3} + C_5$. Are you sure that you don't mean to draw the Cartesian product of $K_{1,3}$ and $C_5$? If this ...


1

Here is my attempt at a Python implementation (2 or 3) of gf3 and gf5. I am only using builtin libraries, so hopefully that will encourage others to play with this. My results agree with the above for $1\leq n \leq30$ and $n=50$ but this will obviously need verification. The performance of gf5 is not great, over 400 seconds for $g_{55}(u)$ alone. I ...


1

I'm not too sure what the etiquette is on Math SE regarding answering old questions but I stumbled across this question and felt it would be good to drop an answer for future users that happen to ask the same question in the future. Anyways, I'm going to do the particular case when $\delta(G) = 3$ and show that there exists a path of at least length 3. This ...


3

Every Directed Acyclic Graph (DAG) on $n$ vertices with the most edges possible is isomorphic to a graph like this: Let $f(n)$ denote the most edges that a DAG $G=(V,E)$ on $n$ vertices can have. Claim: We have that $$f(n)=\frac{n(n-1)}{2}.$$ Moreover, any DAG on $n$ vertices with $f(n)$ edges is isomorphic to the following graph: $$V^*(n) = ...


0

Let $I$ be a maximal independent set. Then, for $e\in E(G)$, $e$ has at least one vertex not in $I$. Hence $V(G)\setminus I$ is a vertex cover. Suppose $V(G)\setminus I$ is not a minimal vertex cover, then there is $v\in V(G)\setminus I$ such that $(V(G)\setminus I) - v$ is a vertex cover. This means that all vertices in the neighbourhood $N(v)$ of $v$ are ...


0

For undirected graphs, constant weight of neighboring vertices has been called "weighted-regular", generalizing the concept of regular graph (when all the vertex weights are equal). That definition is not used often enough to have become a standard term.


0

Think of the blocks of $G-v$. Assume it has a leaf block B (what about the other case?). How do the two internally disjoint paths connecting an "internal" vertex of B with some vertex in another block look like?


0

As in Dirac, build to a maximal counterexample. That is, let $G$ be a bipartite graph with $\delta(G) > \frac{k}{2}$ and no Hamiltonian cycle. If any edge can be added to the graph that preserves all these properties, then do so. Since $G$ is now a maximal counterexample, it has a Hamiltonian path $x_0 \cdots x_n$ (without loss of generality, $x_0 \in ...


0

I found very useful material in the following documents. Newman, structure of complex networks http://arxiv.org/abs/cond-mat/0303516 Newman, random graphs as models of networks http://www.santafe.edu/media/workingpapers/02-02-005.pdf Callaway at al. Network Robustness and Fragility: Percolation on Random Graphs ...


2

The statement given is false, consider the counterexample: cycle $C_5$ of length five, its complement is also $C_5$, thus both are non-bipartite.


2

Form a graph with 21 vertices corresponding to the points and edges between pairs of points more than 120 degrees apart. This graph is triangle-free. The number of edges in a triangle-free graph on 21 vertices is (uniquely) maximized for the bipartite graph on 10 + 11 vertices which has 110 edges. Therefore, there are at least ${21 \choose 2} - 110 = ...


0

Since the angle subtended by any 2 adjacent points is $360^\circ/21$, we need to have a 7 point gap to subtent an angle of $360^\circ/21 * 7 = 120^\circ$. Hence, 8 adjacent points subtend $120^\circ$, and any smaller number of points will subtend $<120^\circ$. So, we can pick $8, 7, \ldots 2$ adjacent points and they will all subtend the angle we want. ...


1

Let $G$ be a graph on 6 vertices. Pick one vertex $v$, and think about the edges connected to it. There are five other vertices, so either there are at least 3 edges incident to $v$ in $G$, or there are at least 3 edges incident to it in the complement $G^c$. Now consider the three vertices that $v$ is connected to in either $G$ or $G^c$. Think about ...


2

You are correct. There might be an $NP$-complete problem that can only be translated into Hamiltonian path problem in $\Omega(n^{10})$ time, for instance. In which case an $\Omega(n^{10})$ translation and an $O(n^4)$ solution gives a total time of $\Omega(n^{10})$. The only thing you can be certain of is that the final time is bounded by a polynomial.


1

There are 7 vertices other than $A$ and $B$ in the graph. So, if you want to count the number of paths of length $m+1$ ($1 \le m+1 \le 8$) between $A$ and $B$, you must choose $m$ vertices from those 7 vertices and the arrange them in an order (so you will have a path starting at $A$, going through those $m$ vertices in that specific order and ending at ...


0

Note that $\chi'(G) \geq \Delta(G)$ be definition. So it is sufficient to prove the case that $\chi'(G) = \Delta(G)$ is impossible. I prove by contradiction below. Proof: Assume $\chi'(G) = \Delta(G)$. We then have $$ |E(G)| > k \cdot \chi'(G) $$ By Pigeonhole principle, there exists a color $c$ such that at least $k + 1$ edges of $G$ are of color $c$. ...


0

Given a square of size $n \times n$, where $n \in \mathbb{Z^+} $, the smallest value of shaded squares $N$ can be determined as one of these three cases: If $n \equiv 3k \equiv 0 \mod 3$, then $N = 3k^2$ If $n \equiv 3k +1 \equiv 1 \mod 3$, then $N= 3k^2 + k + 2*\lfloor\frac{3k+1}{4}\rfloor$ If $n \equiv 3k +2 \equiv 2 \mod 3$, then $N= (3k+2)(k+1)$


1

The thing is that the Cayley graph is not canonical : for a given group $G$, each choice of a generating set will give a different Cayley graph. And every group with at least $3$ elements has a Cayley graph with triangles : if $x\neq y$ in $G$, put $x$, $y$ and $xy^{-1}$ in the generating set, and this will give you a triangle in the Cayley graph. On the ...


1

The easiest way to do this is with the probabilistic method. I'll give you a quick outline: Prove that every triangle-free graph has at most $\lfloor n^2 /4\rfloor$ edges. Randomly color each vertex of your graph, independently and uniformly with $\lfloor 2 \sqrt{n} \rfloor$ colors. Calculate the expected number of edges that are incident on vertices of ...


1

You are overcounting in your case 3, since choosing, for example, $\{a,b\}$ or $\{c,d\}$ for the first cycle results in the same graph. Each solution in the class is counted $2!$ times, so is contribution to the result is not $\binom42$ but $\binom42/2!$.


4

You can create $K_{3,3}$ as following: Delete edges $(b,j)$ and $(e,g)$ Contract edges $(a,b)$, $(a,j)$, $(e,f)$ and $(f,g)$. First note that for $K_5$ we need 5 edges with degree 4. That could be possible with edge contraction, but it is very unlikely. So we need to find $K_{3,3}$. To find $K_{3,3}$, we need a graph with six vertices with degree three ...


0

Fact: if the degree of all points is 2 or more, there is a cycle $v_1 \rightarrow v_2 \rightarrow \ldots v_1$ in the graph. (Proof sketch: start anywhere and keep walking, till you meet a vertex you've already seen (which will happen as there only finitely many): there are no dead ends as long as we meet new points because of the degree condition)). This ...


0

You can produce upper bounds for the three cases $n \equiv 1,2,3 \mod{3} $. In a $3n \times 3n$ square the upper bound is $3n^2$ because you can color every third row. In the case that it is a $(3n+1) \times (3n+1)$ square, then the upper bound is $3n^2+ n + 2*\lceil \frac{(3n + 1)}{4} \rceil$. This results from coloring every third row and adding a pair ...


4

Consider an infinite checkerboard with squares labelled by pairs of integers and mark every square whose indices satisfy $$(i,j) \equiv (0,0) \pmod{4}$$ $$(i,j) \equiv (0,1) \pmod{4}$$ $$(i,j) \equiv (2,2) \pmod{4}$$ $$(i,j) \equiv (2,3) \pmod{4}$$ This provides a marking of the infinite board with the desired property such that every fourth square is ...


0

For a proof by contradiction, suppose you have a graph with odd number of odd degree vertices, say $\{v_1,\dots,v_k\}$. Then $d(v_1)+\dots+d(v_k)$ is odd. The remaining vertices $\{v_{k+1},\dots,v_n\}$ have even degrees, so $d(v_{k+1})+\dots+d(v_n)$ is even. Then $\sum_{v\in V}d(v)=[d(v_1)+\dots+d(v_k)]+[d(v_{k+1})+\dots+d(v_n)]$ is odd, since an odd ...


0

The same proof of Forever Mozart explained differently is as follows: Consider that such a graph exists and consider its incidence matrix. The sum of the numbers in column must be $2$ for each edge is incident on exactly $2$ vertices. It follows that the sum of all the numbers in the matrix would be an even number. Now the row sum for odd degree vertices ...


1

You need to prove a little lemma: (1) Sum of evens is even. (2) Sum of odd number of odds is odd. Prove (1) by factoring out a $2$, and prove (2) by induction on the number of terms. Then we can prove what you want. $E(G)=\{v\in V(G):d(v)\text{ is even}\}$ $O(G)=\{v\in V(G):d(v)\text{ is odd}\}$ $\sum_{v\in V(G)} d(v) =\sum _{v\in E(G)}d(v)+ ...


1

Well, any triangle-free regular graph has constant link. Or take the line graph of such a graph.



Top 50 recent answers are included