New answers tagged

0

The number of edges of $K_n$ is $\binom{n}2=\frac12n(n-1)$, so if you’re told that you have $e$ edges, you need to solve $2e=n(n-1)$ for $n$. It’s always true that $n-1<\sqrt{n(n-1)}<n$, so $$n=\left\lceil\sqrt{2e}\right\rceil\;,$$ the integer obtained by rounding up $\sqrt{2e}$. For values of $2e$ with no more than four digits, $n$ will be a two-...


0

If you can estimate square roots, you can try the following approach: If there are $v$ vertices and $e$ edges in a complete graph, then we have $e=\frac{v(v-1)}{2}$. So $2e=v^2-v$. But also $v^2-v$ is between $(v-1)^2$ and $v^2$. That is, $(v-1)^2<2e<v^2$. So $v-1<\sqrt{2e}<v$. So $v$ can be found by taking the square root of $2e$ and ...


1

In this particular case (number of edges in a complete graph), it's easy, because the number is $\frac12 n(n-1)$. So you have $$n(n-1)=210$$ and $n(n-1)$ lies between the consecutive squares $(n-1)^2$ and $n^2$. So obviously $n=15$. You can use this trick well into the thousands, I would think.


0

You could use guess and check. If a complete graph has $n$ vertices, then it has $f(n) = n(n-1)/2$ edges --- the number of different "handshakes" between $n-1$ people if everyone shakes everyone else's hand. So for example, you could compute various values of $f(n)$: $f(1) = 1$, $f(2) = 3$, $f(3) = 6$, $f(4) = 10$, and so on. You can guess large values for $...


1

The degree one vertex must not be moved. Thus its neighbor must not be moved. This vertex's other neighbors are of differing degree and thus cannot be moved. Similarly the remaining two vertices cannot be moved. Put otherwise we have no non-trivial automorphisms with respect to the topological structure and thus have no candidates for automorphisms on the (...


2

An isomorphism is a map between two relational structures that is a bijection and preserves the relations. In algebra, the relations are the operators. In graph theory, we are dealing with the adjacency relation. So the identity map is an automorphism. More so, the isomorphism relation is an equivalence relation, meaning it is reflexive. So your job is to ...


0

No, You can not traverse an edge twice (or more than twice) in a circuit. The Circuit is nothing but a closed walk with no repeating edge and no repeating vertices(expect starting and terminating vertices). For more info you can refer following link. What is difference between cycle, path and circuit in Graph Theory


0

Pages 78-79 on unchielded collider or immortality. They should be synonyms.


1

There are some corner cases for which your algorithm doesn't work. For example: What if some vertex is a part of a negative cycle unreachable from $s$ (your problem statement doesn't say anything about it, so we have to assume the worst case)? Your inequality might be satisfied even for vertices that are reachable from negative cycles, but doesn't belong ...


0

Because L comes after K in the alphabet. See Cuntz-Krieger algebras of directed graphs. Alex Kumjian, David Pask and Iain Raeburn Graphs, groupoids and Cuntz-Krieger algebras. Alex Kumjian, David Pask, Iain Raeburn, Jean Renault


0

Let $S_1,\ldots,S_k$ be the seminars and $s_i$ the number of applications for seminar $S_i$. Split each seminar in $\lceil \frac{s_i}3\rceil$ parts of size at most 3, except the two seminars that had 40 applications, which we split in 12 parts of size 3 and 1 part of size 4. Note that each seminar is split in at most 13 parts. Consider the $A,B$-bigraph ...


1

You can think of an alphabet $\Sigma$ as simply a set of "letters". Any set can be used as an alphabet. A word in the alphabet $\Sigma$ is an ordered list of symbols $w_1w_2\ldots w_n$ where each of the $w_i \in \Sigma$. Given any two words $u$ and $v$ made from the same alphabet $\Sigma$, you can form their concatenation $u+v$, which is just the word made ...


1

If every cycle has length at least eight, then every face in your crossing-free embedding is bounded by at least eight edges, so $8f < 2|E|$, or simply $4f < |E|$. Combining this with Euler's characteristic formula, $$\begin{align} |E|=f+|V|-2 &\implies 4|E| = 4f + 4|V| - 8 \\ &\implies 4|E| \leq |E| + 4|V| - 8 \\ ...


1

If a planar graph $G$ contains no $3$- or $4$-cycles, then given a planar embedding of $G$, every face is bounded by at least $5$ edges. Then since every edges is incident to exactly two faces, we have $5f \leq 2e$. Combining this with Euler's characteristic formula, $$\begin{align} f-e+n = 2 &\implies 5f-5e+5n = 10 \\ &\implies 2e-5e+...


1

Since no one immediately answered this question, I suspect that there are no standard terms for the number of descendants or the number of ancestors of a given node in a directed acyclic graph (DAG). But remember that the point of writing is just to clearly convey an idea to the reader, so you should feel free to invent terms as you need them, just so long ...


1

A graph $G$ is $d$-inductive if either $G$ has at most $d$ vertices or $G$ has a vertex $u$ of degree at most $d$ such that $G \setminus\{ u\}$ is $d$-inductive. Equivalently, $G$ is $d$-inductive if its vertices can be numbered so that at most $d$ neighbors of any vertex $v$ have higher numbers than $v$.


3

There is an index of notations in the book on page 573. If you look up "$\Delta$" in it, you see that this is the symmetric difference of sets: $$X \mathbin\Delta Y = (X \setminus Y) \cup (Y \setminus X).$$ It does not appear to be an operation on graphs, just on sets.


1

The answer seems to be $$\sum_{k=1}^N\binom Nk2^{(N-k)k}.$$ First choose a number $k\in\{1,\dots,N\},$ the number of vertices. Next choose a $k$-element set $K\subseteq\{1,\dots,N\}.$ For each $i\in K$ choose a set $S_i\subseteq\{1,\dots,N\}$ subject to the conditon that $S_i\cap K=K\setminus\{i\}.$ In other words, $S_i=(K\setminus\{i\})\cup T$ where $T$ ...


2

Yes your ideas are correct. For the sake of not leaving this question unanswered, I'll refine your proof a bit. Proofs in graph theory have a tendency to naturally be broken into cases like your proof above. A lot of the time though, this isn't necessary, and you can make a proof more concise by trying to combine cases. For example, in your proof, ...


1

One way to quantify the complexity of a data structure (like your graph) is to determine its compressibility or "information content" as defined by Algorithmic Information Theory. What you'll need to do is encode each graph into a binary string. A simple convention is give here, where adjacency matrix is transformed into a string of trinary-values elements. ...


0

The threshold function is $f(n) = 1/n$ for each of your cases. In fact, Łuczak proved that if $v_1$ denotes the number of vertices of degree 1 in $G(n,p)$, then for $n p \to \infty$, w.h.p. $G(n,p)$ contains cycles of all lengths $r$, $3 \leq r \leq n - (1+\epsilon)v_1$. In particular, since $v_1$ is concentrated around its mean for this range of $p$, we ...


1

If you have $23$ nodes then there are $\binom{23}{2} = 253$ possible links, assuming that any node may be linked to any other. If you had $24$ nodes there would be $\binom{24}{2} = 276$ possible links, so $23$ nodes is the most you can have if every pair of nodes must have a unique integer identifier $n$ in the range $0 \leq n \leq 255$. Number the links as ...


3

No, not even if you strengthen "surjective" to require that every edge in $H$ is the image of at least one edge in $G$. For example, take $G=C_{10}$ (clearly planar) and $H=K_5$ (well known not to be); then a surjective homomorphism $f:G\to H$ would be given by $$ \begin{matrix}f(0) = 0 & f(1)=1 & f(2) = 2 & f(3)=3 & f(4)=4 \\ f(5) = 0 & ...


0

For x,y in [1..10] you could map AxAy to 10M+m, where M=max(x,y) and m=min(x,y) -This yields a number in [11..110] which is guaranteed in [0..255] -AxAy maps to the same number as AyAx since changing order doesn’t affect max or min -Distinct unordered (x,y) pairs always map to different numbers (since they must differ in either max or min, and per the ...


1

You could proceed in two steps: First, find the different matches over a set of runs: In terms of graph theory, you are looking for 10 distinct matchings with maximum cardinality in which vertices represent teams, and edges represent games between teams. In other words you want to color all the edges of a complete graphe with 12 vertices, with 10 colors, ...


0

Recall Euler's characteristic formula $f-e+v=2$ for a planar graph. So by the information given we have $8-e+12=2$. Then using the number of edges, the handshaking lemma, and the fact that the graph is $k$-regular, we can find $k$.


2

The slickest proof I've seen for this fact uses an entropy argument. The idea is to let $X = (X_1,\ldots,X_n)$ be a uniformly random vertex in $M$ and upper and lower bound the entropy $H(X)$. Using the chain rule and the fact that conditioning never increases entropy, we have \begin{eqnarray} \log_2|M| = H(X) = \sum_{i=1}^n H(X_i\mid X_{< i}) \...


2

Obviously the definition of two edges being adjacent would be different from the definition of two vertices being adjacent. The only example you've given is that two adjacent edges are also said to be incident. Incident and adjacent are almost synonymous and I don't think you've really pointed out enough examples of overlapping or seemingly random terms. ...


2

The most common way to express this is that component $c_1$ is not simply connected (it has a hole). Of course, this doesn't help to give a term for $c_2$, but in analogy with political maps, we might call it an enclave.


0

If $G$ is a graph of order $6$ with no isolated vertices, and if $G$ has four independent vertices, then $\alpha(G)=5$ or $\alpha'(G)=2.$ Proof. Let $u,v_1,v_2,v_3$ be four independent vertices, and let $x,y$ be the other two vertices. Clearly $\alpha(G)\le5$ (since there are no isolated vertices), and $\alpha'(G)\le2$ (since every edge has at least one ...


0

Let $\{S=a,b,c,d\}$ be an independent set of size 4 and let $u,v$ be the remaining vertices. If $\alpha(G)=5$, then we are done, otherwise there must be an edge from $u$ to $S$ and an edge from $v$ to $S$. If $u,v$ are not adjacent and further if there's only one such edge for $u$ and one such edge for $v$ and both are to the same vertex, say $a$, then, $\{...


1

Assuming that $G$ has no isolated vertices: A vertex (say $v_1$) of degree $\Delta$ will provide cover for all connected $\Delta$ edges, which are associated with a total of $\Delta +1$ nodes. That is to say, for each vertex in the cover, it can "represent" no more than $\Delta+1$ nodes in the graph. And every vertex must be "represented" in some way ...


3

You could say that a digraph has this property if and only if all connected components are strongly connected. I'm not sure if there is one word for it.


0

Is it the conditions of the euler circuit that doesn't make sense? Because if it does then the algorithm should make sense. In general the degree should be even on each vertex because you need a way to go from one to another while traversing each edge. Having even makes it such that you can enter from one way and exit another. Same goes for having a ...


1

Considering network and complex systems applications such as the study of dynamics was a sufficient answer for me after learning basic graph theory. Although some of the further applications of network theory are not quite as 'clear', network theory is really where graph theory has been driven, giving way to new interesting research. Protein networks, ...


1

Ecological networks model interspecies relationships in an ecosystem. Nodes are species, and edges describe interspecies interactions of various types. A specific example is a food web in which the interactions are feeding relationships.


-1

Partial solution: If there are only a finite number of hats of a certain color, then everyone would see that and should say the opposite color.


3

How about molecules? The atoms are the nodes and the bonds are the edges. Or the nervous system? Receptors and the brain are nodes, neurons are edges


3

I will show that, if $G$ is any graph, then the Cartesian product $G\times K_2$ has a perfect matching. (In particular, $C_n\times K_2$ has a perfect matching for any $n\ge3.$) Suppose $G$ is a graph of order $n.$ Let $\overline{K_n}$ be the complement of the complete graph $K_n,$ i.e., $\overline{K_n}$ is a graph with $n$ vertices and no edges. It is easy ...


1

If the number of vertices is even, say $2m$, we may label any vertex with an element of $\mathbb{Z}/(2m\mathbb{Z})$ and draw and edge between two vertices iff the difference between their labels lies in $\{1,3,5,\ldots,2m-1\}$. In such a way we have a $m$-regular graph with exactly $m^2$ edges and no triangle, essentially because the sum of three odd ...


0

Construct $K_{\lfloor\frac{n}{2}\rfloor, n - \lfloor\frac{n}{2}\rfloor}$, the complete bipartite graph in which we split the vertices in two sets, as evenly as possible. After a little calculations you should be able to get that the number of edges is $\lfloor\frac{n^2}{4}\rfloor$, which is the maximum possible for a triagular-free graph by Turan's Theorem ...


0

Let $\nu(G)$ denote the maximum size of a matching in $G=(V,E)$ and $\rho(G)$ the minimum number of edges needed to cover all vertices of $G$. We want to show that $\nu(G)+\rho(G)=|V|$. Note that we need to assume that $G$ has no isolated vertices, for otherwise $G$ does not contain a set of edges covering all vertices. Let $M \subseteq E$ be a maximum ...


1

Here is an example to disaprove the inequality. For a complete bipartite graph $K_{3,4}$, $\lambda (K_{3,4})=3$ and $\chi (K_{3,4})=2$.


3

If $\lambda$ denotes the edge connectivity, then what is $$\lambda(K_{m,n}) , \chi(K_{m,n})?$$


3

The theorem says that a connected simple graph has an Euler circuit if and only if each vertex has even degree, and indeed that graph, in which vertices $A$ and $D$ have degree $3$, has no Euler circuit: there is no walk that traverses each edge exactly once and returns to its starting vertex. A companion theorem says that a connected simple graph has an ...


0

In general, calculating the list chromatic number for a graph is difficult. For the complete graph $K_3$, it is easy though if we make a few easy observations. Let $G$ be a simple graph and let $\chi_\ell(G)$ denote its list chromatic number. Then $$\chi(G)\leq\chi_\ell(G)$$ since we can think of a proper $k$-coloring as a proper list coloring where each ...


2

Clearly, since the sum of degrees across the 9 vertices must be even, there must be a vertex with degree at least $6$, meaning that only 2 vertices are isolated from this vertex. Choose the vertex of highest degree (degree-$6$ or higher) and label it as $A$ and the vertices connected it, the "linked set", as $\{B,C,D,E,F,G\}$. Each of these will have an ...


2

If $\chi(G)=3$, the graph cannot contain any $K_4$ as a subgraph: The above graph is just a $K_9$ with only $9$ edges removed, in particular a $K_{3,3,3}$, with chromatic number $3$, as clear from the picture (no couple of vertices with the same colour is joined by an edge, but the graph has plenty of embedded triangles). On the other hand, it is not ...


5

The complete tripartite graph $K_{3,3,3}$ is a $6$-regular graph on $9$ vertices and has chromatic number $3$ so it contains no $K_4.$ By Turán's theorem, a simple graph with $9$ vertices and more than $27$ edges must contain $K_4$ as a subgraph, and $K_{3,3,3}$ (also known as the Turán graph $T(9,3)$) is the unique $K_4$-free simple graph with $9$ vertices ...


0

You are correct, a path that visits every node(vertex) once is called a Hamilton path. If this path, ends on the same vertex it started it is called a Hamilton cycle. The number of Hamilton paths will depend on the edges that connect these vertices(nodes). For a general graph, finding a Hamilton path is NP-complete: https://en.wikipedia.org/wiki/NP-...



Top 50 recent answers are included