Tag Info

Hot answers tagged

3

First of all, a diagram in $\mathcal{C}$ is not the same thing as a directed graph. A $\Gamma$-shaped diagram in $\mathcal{C}$ is a morphism of graphs $\Gamma\longrightarrow U(\mathcal{C})$, where $U(\mathcal{C})$ denotes the underlying directed graph of $\mathcal{C}$ ${}^{1)}$. Secondly, it makes sense to talk about commutativity for all kinds of graphs. ...


3

Not necessary, consider the directed graph on $A,B,C,B',C'$ with arcs $A\to B$, $B\to C$, $A\to C$, $A\to B'$, $B'\to C'$, and $A\to C'$. This directed graph is a counterexample to your claim since $A\to B$ and $A\to B'$ do not lead to a common vertex. P.S. Combinatoric is not a word, combinatorial is.


2

You can use the Nash-Williams arboricity theorem (see here), in particular, for any subgraph $H \subseteq G$ we have \begin{align*} \left\lceil\frac{|E_H|}{|V_H|-1}\right\rceil &= \left\lceil \frac{\frac{1}{2}\sum_{v \in V_H}\deg_H(v)}{|V_H|-1}\right\rceil \\ &\leq \left\lceil ...


2

We first show that any embedding of $K_8$ into the torus must be a $2$-cell embedding (that is, the complement of $K_8$ in the torus consists of some number of regions/faces homeomorphic to open disks). We can 'build' such an embedding in pieces, but first embedding an $8$ vertex tree on the torus (clearly possible), and then adding edges between two ...


2

This is a consequence of the Heawood Conjecture, which gives a formula for the maximal number of colors needed for a graph coloring of a surface with a given genus---called the chromatic number of such a surface. Despite its name, was settled positively in 1968 by Ringel and Youngs. (The genus $0$ case is precisely the topic of the celebrated Four Color ...


2

Once you have an algorithm for deciding whether two graphs are isomorphic, you can use it to find the isomorphism whenever one exists. Given isomorphic graphs $G$ and $H$, let $v$ be the first vertex of $G$ (meaning "first" in the ordering used to present the graph, for example as a matrix), and check, for each vertex $w$ of $H$ whether the induced ...


1

I provide a complete answer here. I try to give them in a "hint"-ish order, so that you can just read a prefix of my answer for a hint. Suppose the minimum degree is $k$. I will show that there must exist a node $a \in A$ such that there exists at least $k$ different nodes $b \in B$, such that there exists a perfect matching in $G$ that includes $(a, b)$. ...


1

If it is a finite graph, the answer is yes, because for fixed $n$ there is only a finite number of paths of length $n$ in the graph. For example, you can enumerate all $n$-tuples of distinct vertices in the graph, check whether they form a path, compute the hash value of that path if they do, and check if that hash occurs in your list of hashes.


1

Using your definition of the modularity of -1/n, an example of a network with -1 modularity is simply a network with only one node. When $n = 1$, $-1/n = -1/1 = -1$


1

I was thinking long and hard about it and I realised that induction can be applied: for n=3 It's obvious we have three vertice $ v_1 , v_2, v_3 $ Highest possible degree here could be 2 so: $ V_1=v_1 $ $V_2$={$v_2, v_3$} Suppose that the claim is true for all m where m < n: Let'a look at our G=(V,E) where |V|=n. Take a vertex $ v\in V $ such v has the ...


1

For $m,n\in\mathbb{N}$, $\text{Aut}\left(K_n\right)\cong S_n$ and, if $m \neq n$, $\text{Aut}\left(K_{m,n}\right) \cong S_m\times S_n$, whereas $\text{Aut}\left(K_{n,n}\right)\cong C_2\times S_n^2$, where $C_k$ and $S_k$ are the cyclic group of order $k$ and the symmetric group on $k$ elements, respectively. If your complexity is the size of the ...


1

Since you want a non-inductive argument, I shall provide one. The statement to be proven is as follows: Let $G(V,E)$ be a triangle-free graph on the vertex set $V$ with the edge set $E$. Suppose that $E$ can be partitioned into two sets $E_1$ and $E_2$ such that the edge-induced subgraph $G\left[E_1\right]$ is planar, while $G\left[E_2\right]$ is a ...


1

Solution follows, stop reading if you want to figure it out yourself. Order nodes so that the leaf comes first and its neighbour comes next. Claim. $1, 1, -1, -1$ cannot be balanced. Proof. Suppose that in step $0$ we have the above and in step $n$, where $n$ is minimal, we have $0, 0, 0, 0$. In step $n-2$ we must have $a, -a, a, -a$ (or the last two ...


1

There are many books for graph theory, and you should select the topics that suit the education goals of the course. For example, in computer science the Graph theory algorithms is highly considered as main topic in each graph theory course. Personally, I prefer the following two books: Introduction to Graph Theory Graph Theory (Graduate Texts in ...


1

Partial answer: If $n$ is prime, then every vertex-transitive graph with $n$ vertices is isomorphic to one of the form that you have given, because every transitive permutation group of prime degree $p$ contains a $p$-cycle. In general, the property that divides the vertex-transitive graphs into these two classes is whether the automorphism group of the ...


1

I drew UG and added six more isolated vertices. Now, in G' K6 is a subgraph and therefore G' is nonplanar.


1

The indifference condition in mixed strategy NE does not imply $a=b=1/2$. Here is an example: $\hskip1.8in$ First, note that since there are three actions for player 1, there are technically seven possible supports for his strategy: UCD, UC, UD, CD, U, C, D. Similarly, there are are seven possible supports for player 2. Therefore, there are in fact 49 ...



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