Tag Info

New answers tagged

0

If I take a graph with vertex set $\mathbb{R}$, and connect 0 to every $x \in \mathbb{R} \setminus \{ 0 \}$, then I have uncountably many finite paths from 0. If on the other hand you require the vertex set to be countable, then the number of finite paths from any given point is countable. (As it is a countable union of countable sets). As Tryss says, if ...


1

In the Cayley graph, each of the edges corresponds to multiplication with one of the generators -- in one direction. In the other direction, the edge corresponds to multiplication with the inverse of that generator. Thus, every edge can be traversed in either direction -- that's what the $\epsilon_i=\pm1$ exponents in the proof you show are for. In other ...


0

Note that a graph is not tree if and onlt if it includes a cyle. But that means that a word $a_1a_2..a_n=1$. Hence the group is not free. When a group is not free then it must have none trivial relation satisfied by generaters with $a_1...a_n=1$. Hence, we have a cyle in the corresponding graph.


1

A graph is only called a tree when it is acyclic as an undirected graph, so the directions of the edges are irrelevant when considering whether a graph is a tree. An acyclic directed graph need not be a tree, as you illustrated with your worries about the proof; a cycle may exist that is not a directed cycle.


0

To see that the first definition implies the second, you can use induction on $n$, the number of vertices. The base case is trivial. For the induction step, the cograph $G$ can be obtained either by the union of two smaller cographs $G_1$ and $G_2$, or by complementing such a graph. In the first case, apply induction on both $G_1$ and $G_2$ to deduce that ...


6

In fact, "Roughly speaking, category theory is graph theory with additional structure to represent composition." is a good summary of the connection between the notion of a graph (meaning here: directed multigraph) and the notion of a category. Here is a way of how to make this precise: Let $O$ be a set ("set of vertices"). Then we have a category ...


2

Category theory and graph theory are similar in the sense that both are visualized by arrows between dots. After this the similarities quite much stop, and both have different reason for their existence. In category theory, we may have a huge amount of dots, and these dots do often represent some abstract algebraic structure or other object with some ...


0

Starting with $K_4$ you can construct an infinite family. Write down the 6 Kempe chains as 12,13,14,23,24,34. Note that only 3 vertices occur at the end of the chains. Add a vertex in the center of these 3 vertices and connect it to each of them (triangle 234 in this case). Your new Kempe chains are 121,131,141,23,24,34. This repeats indefinitely. At ...


0

It seems not true to me. By adding the identity matrix you add some path in your graph hence change $A^*$. For example consider the graph with two node and only one edge between them represented by the matrix $A=\begin{pmatrix} 0& 1\\ 0&0\end{pmatrix}$. You have: $$ A^*=\begin{pmatrix} 0& 1\\ 0&0\end{pmatrix}$$ however $$ (A\oplus ...


1

First look for a group $g$ such that there exists a vertex $a$ that is twice on the same side of two edges i.e. for which there is the two lines $a$ $b_i$ $g$ and $a$ $b_j$ $g$ or $b_i$ $a$ $g$ and $b_j$ $a$ $g$. From this two lines you know that $b_j$ and $b_i$ must be below $a$ in the tree hence you change the the direction of the group if needed so that ...


0

Here's an example of determining whether a graph is Ramanujan using Maple. I'll take a random $5$-regular connected graph with $20$ vertices. with(GraphTheory): G:= RandomGraphs:-RandomRegularGraph(20,5,connected); A:= AdjacencyMatrix(G); P:= factor(LinearAlgebra:-CharacteristicPolynomial(A,t)); $$ \left( t-5 \right) \left( ...


1

We will count certain connected subgraphs of a "master graph" like a chess board, namely a rectangular grid of size $m\times n$ vertices (rows by columns) with $m\cdot(n-1)$ horizontal and $(m-1)\cdot n$ vertical edges. All of our graphs will be simple, i.e. the edges are undirected and may be identified by an unordered pair of distinct vertices. Thus ...


1

Let $S_u=\{M\mid M\textrm{ is a matching with }u\textrm{ is }M\text{ unsaturated and there is no augmenting path starting at }u\}$. $S_u$ is nonempty by the assumption. Take $M^*\in S_u$ with maximum number of edges. Suppose that $M^*$ is not a maximum matching, then there is some augmenting path $P=v_0e_1v_1e_2v_2\dots v_{k-1}e_kv_k$ in $M^*$. By the choice ...


0

Closures of sets in a matroid are flats. I forget the textbook definition of the closure operation, but intuitively, you can think of $\mathrm{cl}(X)$ as the union of $X$ and the set $\{e \in M : X \cup e$ has a new circuit that's not entirely in $X \}$. So the question is, what does deletion and contraction do to circuits? If $C$ is a circuit and $e \in ...


3

The complete $K_{17}$ would have ${17\choose 2}=136$ edges. So we are missing only $7$ edges. Thus every vertex has degree at least $16-7=9>\frac{17}2$.


0

Proven in: Ringel, G. "Das Geschlecht des vollständiger Paaren Graphen." Abh. Math. Sem. Univ. Hamburg 28, 139-150, 1965. Harary, F. Graph Theory, Reading, MA: Addison-Wesley, 1994, page 119.


0

Not really an application per se, but rather a connection with the notion of strong regularity and the isomorphism problem. What follows is just a shallow description but I can add references/expand if you need something more. It is well known that if a graph has many different eigenvalues (multiplicity of eigenvalues is bounded) then the isomorphism ...


2

I see now! If $f(x,y) < c(x,y)$ for some $(x,y) \in (X,\overline{X})$ or $f(x,y) = 0$ for some $(x,y) \in (\overline{X},X)$, then the value of the flow is less than the capacity of a cut. This contradicts the max-flow min-cut theorem. More precisely: Let $F$ be the value of a maximal flow, $(X,\overline{X})$ a cut, and suppose $f(x,y) < c(x,y)$ for ...


1

I think the first part of this Proposition may be wrong. Take for example $G$ to be the dihedral group of order $12$ with presentation $G=\langle r,s\mid r^6=s^2=(rs)^2=1\rangle$. The center is $\{1,r^3\}$ with order $2$ so $\Gamma$ has order $10$. Now take $S$ to be all vertices except $r$ and $r^2$. This is a cut-set since $r$ and $r^2$ commute and thus ...


1

Let $G$ be a graph with $n$ vertices. Suppose vertex $v$ has degree $d$ in $G$, what will its degree in the complement of $G$ be? Out of the $n-1$ other vertices $v$ is adjacent only to the $n-1-d$ to which $v$ is not adjacent in $G$, so this degree is $n-1-d$. Now if $G$ is regular all the vertices have common degree $d$ in $G$, and so they all have degree ...


1

Let $G$ be a regular graph, that is there is some $r$ such that $|\delta_G(v)|=r$ for all $v\in V(G)$. Then, we have $|\delta_\bar{G}(v)|=n-r-1$, where $\bar{G}$ is the complement of $G$ and $n=|V(G)|$. Hence, the complement of $G$ is also regular.


1

It means that it forms a cycle once you add $uv$. This is true precisely when there is a path between $v$ and $u$ in $G$. To form the cycle, go from $v$ to $u$, add in the edge, follow it and end up back where you started at $v$.


2

That theorem is meant to be read as follows: "For all planar graphs G, there exists a vertex $v$ of $G$ with degree $5$ or less." You are reading it as "For all planar graphs G and for all vertices $v$ of $G$, $v$ has degree $5$ or less"


1

relax the edges once in increasing order and once in decreasing order.


2

When a group acts on a graph (in the usual sense), there is more structure than just a permutation of the vertices. Specifically, it not only maps vertices to vertices, but preserves the property that if there is an edge $(a,b)$ in the graph, then there will be an edge $(g(a), g(b))$ as well. That is, it permutes both the vertices and edges in a compatible ...


1

I think your problem can be reduced to just looking at matching-covered graphs. Let $G$ be a graph and let $\mu$ be its matching number. Let $S$ be the set of all vertices covered by all maximum matchings. Let $G'$ be the larger graph obtained by adding a new independent set of size $|V(G)| - 2\mu$, adjacent to the vertices of $V(G)-S$. If $G'$ is ...


2

The the Edmonds-Gallai decomposition could be what you're looking for. It decomposes a graph into sets $A$, $B$ and $C$, where $A$ is all the vertices missed by at least one maximum matching, $B = N(A)$, and $C$ is all other vertices. Basically, every maximum matching matches vertices in $B$ to odd components of $G - B$ in $A$. In $G - B$, $C$ consists ...


1

Let $v,e,f$ be the number of vertices, edges and faces. So by your given condition, we have $ e = 5v/2 , f = 5v/3 $. And use this in the euler characteristic formula for sphere $ v-e+f =2$ to get $v (1-5/2+5/3) = 2 \implies v = 12 $. So there are only one such triangulation.


0

I suppose you already know that a strongly connected tournament of order $n\gt1$ must contain a $3$-cycle. (If the tournament has no $3$-cycle, it's a transitive tournament, and not strongly connected.) For the induction step you have to show that, given a $k$-cycle (where $3\le k\lt n$), you can construct a $(k+1)$-cycle. Consider a $k$-cycle ...


0

You can find a very detailed proof in this paper page 15 theorem 4


0

Is it possible that every chicken pecks at least two other chickens (in one step)? No, that's not possible. (Why not?) So there is a chicken that pecks just one other chicken. Call that chicken $A$ and call the chicken it pecks $B$. If $A$ is a king, then $B$ must peck the two remaining chickens, call them $C$ and $D$. Either $C$ pecks $D$ or $D$ pecks $C$, ...


1

Basic definition chasing suffices. Denote by $A$ the adjacent matrix of $H$ such that $$A(y,z) = \begin{cases}1 & \text{if }|y \Delta z| = 1,\\ 0&\text{otherwise},\end{cases}$$ where $y, z\in\mathcal{P}([n])$ and $\Delta$ is the symmetric difference of two sets. Observe $$(Af^x)(y) = \sum_z A(y,z)f^x(z) = \sum_{z:|y\Delta z|=1}(-1)^{|z\setminus ...


2

As your link informs, the numbers are given by: $$a(n) = \lceil\left(3/2\right)^{(n-3) \cdot n \cdot (n-1)}\rceil$$ Which is in accordance with the known numbers $R(1,1),\dots,R(5,5)$ and fall within the limits given here (although there is an even better upper estimate found recently). However, the numbers on your link are not explicitly said to be more ...


1

Hint: Use this definition, "If G is a tree, if and only if G is connected and has $n − 1$ edges." and (assuming G mentioned in question is connected) 1) Find number of vertices in G ($n$) 2) Find number of edges ($e$)(Hint: each edge contribute two degrees) Find if there are any K's such that $e=n-1$. Then it is possible to find a tree of such K. ...


0

If the MST is unique then the answer of user3440448 is correct. Since your notes say "the MST" this seems to be the case. However, note, that if the MST is not unique then statement (1) does no longer hold: Consider a cycle of four nodes $v_1$, $v_2$, $v_3$, and $v_4$ with length 1 for all edges $(v_1, v_2)$, $(v_2, v_3)$, $(v_3, v_4)$, and $(v_4, v_1)$. ...


0

There can't be such a qualifying number. Imagine a graph that meets such a threshold. Then take 3 copies of the graph and link as follows: There is no directed spanning tree for this composite graph although it meets the assumed incoming/outgoing links criteria.


1

Turán's theorem is indeed what you need, because the best way to avoid a subgraph isomorphic to $G$ is to produce a triangle-free graph. According to the special case of Turán's theorem called Mantel's theorem, the maximum number of edges in an n-vertex triangle-free graph is $\lfloor n^2/4 \rfloor$, achieved by creating a complete bipartite graph with the ...


0

Your approach to the first question is entirely reasonable. Since $5\cdot6=30>28$, it’s clear that $6$ wins guarantee advancement. To show that $5$ do not, we need only show that it’s possible for $5$ teams to win $5$ matches each; the arrangement shown by user73985 works fine and is natural enough that it’s the first one that I found as well. (You can ...


0

The $i,j$ entry of this matrix product is $$\tag1b_{i,j}=\sum_k a_{i,k}a^T_{k,j}=\sum_ka_{i,k}a_{j,k}.$$ The product $a_{i,k}a_{j,k}$ is $1$ if verticex $i$ and $j$ are both incident with edge $k$, and $0$ otherwise. Thus for $i\ne j$ the entry $b_{i,j}$ counts the number of edges from vertiex $i$ to vertex $j$ (so for simple graphs, $b_{i,j}$ is $1$ or $0$, ...


2

Consider a complete graph with an even number of vertices, with each edge colored red or green, in such a way that there are no red triangles, each vertex is incident with at least one green edge, and there is no perfect matching consisting of green edges. Let $V$ be the vertex set. Let $M$ be a maximal green matching, and let $W$ be the set of vertices ...


2

The following is not entirely rigorous, since it avoids many convergence issues. But it gives a quick way to see why we expect a certain answer. Connections with Laplacian on the Graph The problem of finding the effective resistance is tied to harmonic functions on graphs in the following way. Start with a graph $\mathcal{G}$. Each vertex represent a node ...


1

If $D$ is the diagonal matrix with the out-degrees of the vertices as its diagonal entries, then $$ MM^T = A + D.$$ The matrix $A+D$ is often called the unsigned Laplacian. On the other hand, $$ M^TM = L +2I$$ where $L$ denotes the adjacency matrix of the line graph. In general there is no useful relation between the spectrum of $A$ and the spectrum of ...


0

Let G be an undirected, weighted, connected graph G. Let $u$ and $v$ be two non-adjacent vertices, and let d$(u,v) = k$. Also, let $P_1 = (u,u_1,...u_{k-1},v)$. Now, assume to the contrary that $\exists$ a path, distinct from $P_1$, from $u$ to $v$ of length $k$. That is, $P_2 = (u,w_1,w_2,...w_{k-1},v)$. Then, by assumption, $P_1$ is contained in the ...


1

Say we're given a path of length $2i$, and we want to find a path of length $2j$ that intersects the first path. We have $2i$ choices for which vertex on the first path the paths intersect at. Call this vertex $v$. We have $2j$ choices for "how far along" the second path $v$ is. That is, pick $0 \leq k \leq 2j - 1$ and say there are $k$ vertices of the ...


0

I only learned of graphical sequences a couple hours ago, and (indepently) discovered the Havel-Hakimi solution through the game here: http://jacquerie.github.io/hh/. I really recommend playing at least a few "rounds" to see how well you understand (or learn) how Havel-Hakimi works. My graph theory classes were a couple decades ago, so I only have an ...


0

I think the paper by Takeaki Uno, An algorithm for enumerating all directed spanning trees in a directed graph, should help you solve your problem.


0

You seem to be thinking in nearly the right way, but you are putting your thinking together in a way that might make it difficult to work with it. First, when constructing the transition matrix, you do not need to consider the initial values. That makes it a bit easier to think about it. For each possible state $i$ (if the animal is at position 1, 2, 3, or ...


1

Proof by induction. This is true for cliques of size 2 by the definition of tree decomposition. Suppose this is true for cliques of size k and you are given a clique S of size k+1. Choose some $v\in S$ and let $S_0=S-\{v\}$. By the hypothesis, there is some $t\in T$ such that $S_0 \subseteq V_t$ - denote by $T_0$ the set of all such $t$'s (which is actually ...


0

I can't quite follow your thinking with "modulate by number of edge that is not compatible to form a cycle of length $i$". That seems to focus on the ways to not form a cycle but the expression is looking at the ways cycles can be formed. $\binom{n}{i}$ is obviously the number of ways to select $i$ nodes from $n$ available. Then, $\frac{(i-1)!}{2}$ is the ...


1

Although the latest edition is fourth, I can only find the third, the definition is on page 6, see the picture for the statement.



Top 50 recent answers are included