# Tag Info

1

Let's assume that you're working with $\mathbb Z$ coefficients. Then $C_1(T)$ is the set of all formal linear combinations $$\sum_i c_i e_i$$ where $e_i$ ranges over all edges of the tree, and the $c_i$ are integers. And $C_0(T)$ is the set of all formal linear combinations $$\sum_j a_j v_j$$ where the $a_j$ are integers and the $v_j$ are vertices. ...

1

For any two graphs $G$ and $H$ we have $$W(G \square H ) = |V(G)|^2 W(H) + |V(H)|^2W(G),$$ where $W(G)$ is the Wiener index of $G.$ Now the hypercube graph $Q_k = Q_{k-1} \square K_2$ and the result now immediately follows by induction.

1

Consider the vertex $\mathbf 0=(0,0,\dots,0)$ of the hypercube graph $Q_n$. For each $r\in[n]=\{1,2,\dots,n\}$ there are $\binom nr$ vertices at a distance of $r$ from $\mathbf 0$, so$$\sum_{v\in V(Q_n)}\operatorname{d}(\mathbf 0,v)=\sum_{r=1}^nr\binom nr.$$Since all vertices of $Q_n$ are similar, the Wiener index of $Q_n$ is equal to$$\frac12\sum_{u\in ... 2 Let \kappa be the minimal number k for which a graph G is k-(vertex)-connected and let \kappa' be the minimal number k for which the graph is k-edge-connected. Then one has \kappa \leq \kappa'; here this means that if a graph G is 3-vertex-connected (\kappa \geq 3) then it also is 3-edge-connected (\kappa'\geq 3). This can be shown ... 0 Note that your definition of a 3-connected graph does not seem to be standard, it would usually be a graph where removing up to 3 vertices does not make it disconnected. Now to your questions: Take a cycle. Removing any vertex never makes it disconnected, but by removing two edges will. 0 Since T is a tree, we have e = n-1. Furthermore, T and \bar{T} together contain all \binom{n}{2} edges of the complete graph K_n. This means that \binom{n}{2} = e + 10 e = 11e = 11(n-1) or \frac{n(n-1)}{2} = 11(n-1), thus n=22 (or n=1 if we consider the empty graph to be a tree as well). 0 Apart from the a miscalculation of the number of edges in the complete graph you had done well. Just wanted to make a couple of things clear. Well first of all there are few better ways to come to a solution to the problem. I would actually venture to say there are non. As you said we have that e = n-1 and 10 e = |E(\overline T)| = |E(K_n) - E(T)| = ... 3 There is a general rule - the mex rule - for computing Grundy values (or equivalent Nim heaps) in Nim-like impartial games. The moves you have available are take one stick or take two sticks. These lead to smaller positions whose values you already know. List those values and find the first number from \{0, 1, 2, 3\dots \} which you cannot reach. This ... 3 For one pile, the 0 positions are the multiples of (2+1), and the G-values must all be 0,1 or 2, so G(n)=(n \mod 3). The Nim addition theory then dictates the G values for the game with several piles. 0 If non-transitive means "never transitive for any triple", that is impossible for a complete tournament (irreflexive, never-symmetric relation) with 4 or more players. The question sounds like an exercise of rediscovering that fact. If partial tournaments are allowed then it can be done with any number of players, just partition them into 3 categories ... 0 Definitely not. First, whenever the graph is directed or undirected does not matter much, since you can put an edge in two directions. Any planar graph can be made into cubic planar graph by expanding nodes into cycles. In such case there are many which are not the same or not even isomorphic. To give a simpler example, this is not true for trees, e.g. ... 0 Take as A two triangles, with vertices RST and UVW. Connect RST cyclically, also UVW. Join R and U by a directed edge. Take as B a hexagon RSTUVW, and join R and U by a directed edge. Graphs A and B are connected. The degree sequences of A and B are the same. But the graphs are not isomorphic, since the first can be ... 0 Consider the graph on A, B, C with directed edges AB, BC, CA, and the graph with AC, BA, CB. If you want the graphs nonisomorphic, take AB, BC, DC, ED, FC versus AC, DC, BD, EB, FC. 1 These two graphs are a counterexample to your conjecture; in each graph, all four vertices have indegree 1 and outdegree 1: To make the example connected, just embed these two graphs into some larger graph. For example: Here the I have added two red vertices and some additional edges. Each result has corresponding vertices with the same indegree and ... 2 Go backward : If from a position, you can reach a node in the kernel, it is not in the kernel. And if a node is not in the kernel, you can reach a node in the kernel from it. So 40,39,38,37 are not in the kernel (by adding 5, you reach 41+) but 35 is (because you can only go to 37,38 and 40 that are not). Go on like that ! 9 Consider the ordered pair, such that \{(x,y)\,|\,x,y\in\{a,b,c,d\}\}. The following relation satisfies those conditions:$$\{(a,b) ,(b,c), (c,d), (d,a)\}$$Clearly, this relation is not reflexive since there is no ordered pair with same members i.e. (x,x). This relation is anti-symmetric since for instance, there is no ordered pair (b,a). This ... 1 "\Leftarrow": We have a set of graphs M such that X=\Gamma(M). Let Y\in X=\Gamma(M). Note that this means that no induced subgraph of Y belongs to M. Now let Z be an induced subgraph of Y. An induced subgraph of Z is an induced subgraph of Y, so it does not belong to M. Consequently Z\in\Gamma(M)=X and we have shown that X is ... 2 If you have a closed path aa, so the end point is equal to the begin point. If this is the only point that is reached twice you are done. If there is another point that is reached twice say v then you can make two new closed paths vv were one goes to a and back and the other is the rest. One has to be of odd length. Repeat this argument with the odd ... 0 Let's first have a look at graphs with edge-preserving maps and graphs with edge-reflecting maps. Given some graph R, we have the dual graph \neg R which has edges exactly where R has no edges. Then f : R \to Q is edge-preserving iff f : \neg R \to \neg Q is edge-reflecting. So, while we do have two different categories here, they are equivalent. ... 0 Hint: This is true only in simple graphs (no loops or multiple edges). Consider some connected component and denote its size by n. There are n vertices, but only n-1 possible degrees. I hope this helps \ddot\smile 0 1 It is true for finite sets but false in general. For example A= \mathbb Z, B=2 \mathbb Z and f(x)=\frac{x}{2}. 2 Is false. You can always create spanning trees by erasing edges from cycles, as long as you start with connected graphs, and you can erase any edge, as long as it is in a cycle. Thus, if you create a spanning three, then start again and ... 0 For 2, consider a square. You can construct a spanning tree by removing any one edge, so there are four. For 3, a very trivial counterexample is A = \{1,2\}, B = \{1\}, C = \{2\}, but you could find more "interesting" ones. For 4, by contraposition, if f is not 1-1, there are x, y such that x \ne y and f(x) = f(y). This makes the given property ... 2 I wouldn't think so. A complete graph should always have a spanning tree. Pick your favorite vertex u from the vertex set V, infinite or not, and construct a giant star tree with u as the center. That is, construct the tree T = (V, F) where the edge set is F = \{uv : v \in V \setminus \{u\} \}. This has to be a spanning tree (and as pointed out ... 0 You need to show one more thing that k \neq 3. That is k=0,1,2. 0 You can consider K forest where K represents number of sources in the graph. In case you have just one source, you can generate 1-forest or forest with one tree. In case you have 5 sources in the graph. Each of the 5 trees in the 5 forest would have one source. No two sources are connected and there is no cycle or loop. Consider it as a set of Octopus trying ... 5 In this case, you can check whether the complementary graphs are isomorphic. The complement to the first graph is two disjoint 4-cycles. The complement to the second graph is an 8-cycle. Since these graphs are clearly not isomorphic, the original graphs aren't either. 4 When the eigenvalues of the adjacency matrices are different the graphs are not isomorphic. 1 Let P=v_0,v_1,\ldots,v_{n-1},v_n be a longest path in T. Clearly v_0 must be an end vertex of T, otherwise we could extend P to a longer path P', which impossible. Now consider v_1. Clearly v_1 is a cut vertex. Now there may be other vertices adjacent to it, but they would have to all be end vertices as well, otherwise we could extend P ... 1 Since the walk should stop at B, let A be the adjacency matrix of your graph without the B vertex. The powers of A, i.e. the matrix elements (A^k)_{km} represent the number of ways from vertex k to m. We look at the elements (A^k)_{05} and (A^k)_{06}, because with one more step we can reach B. EDIT If you need paths without ... 3 Suppose v is a cut vertex. Consider the smallest component A of G-v. Each a \in A has at most (|A|-1)+1=|A| < \frac{n}{2} neighbours in G, contradiction. 0 It's difficult to claim an average because there exist many possible infinite length paths that never reach B. You may want instead to calculate the probability that you have reached B after n steps. @draks ... is on to something, but if you're going to determine the probably that you have "seen" node B after n steps, then you definitely need ... 0 To answer my own question, it appears that (see this paper) having 2n edges suffices. 2 Since T has order n \geq 3 the average degree of T equals \frac{2(n-1)}{n} > 1. It follows that not every vertex of T is a leaf (an end vertex). Consider the tree T' which we get by removing all leaves from T. Since T' is a tree, it has some leaf v. This vertex has the right property, as it has at most neighbor in T' and every other ... 1 Hint: Think about the group (\mathbb{Z}_{17},+) of integers modulo the prime number 17, and consider the sequences (0,k,2k,3k,\ldots,16k) for k=1,2,\ldots,8. 1 Since \delta \geq 3, the number of edges is greater than or equal to \frac{3n}{2}. Therefore f=2+e-n \geq 2+\frac{3n}{2}-n = \frac{n}{2}+2. Thus (i) is true and (iv) is not true because \frac{n}{\delta+1} < \frac{n}{2}+2. 1 Is it that a graph is necessarily non-planar if a subgraph of K3,2 or K5 corresponds to one of its possible subgraphs? The graphs K_{3,3} (not K_{3,2}) and K_5 are non-planar. If we subdivide the edges in a graph (essentially replacing edges with paths), we don't affect planarity. So any subdivision of K_{3,3} or K_5 is non-planar. ... 0 The theory of force directed drawing algorithms(further theory of Tutte's barycenter method ) is the way to solve it if is planar...if is not you drop in the previous answer. BtW cool game :) 0 Might consider making each unique class-discussion-lecture date object into a matrix like this: 5 For c), consider an equilateral triangle. Of course a) and b) are harder. A useful fact is the following characterization of bipartite graphs: a graph is bipartite if and only if it contains no odd cycle. Hence it suffices to show that the graph G from a) has no odd cycle. Suppose there is a cycle (x_1,y_1), \ldots, (x_m,y_m), (x_1,y_1) where ... 1 1) Yes, people use these terms interchangeably. The advantage of k-cube is that it makes explicit what the dimension is. On the other hand, the term hypercube sounds way cooler. 2) No! Two graphs G and H are isomorphic if there is a bijective function from the vertices of G to the vertices of H with the property that two vertices are joined by an ... 2 Let P=v_0v_1 \dots v_l be a longest path in G. v_0 has to have additional neighbors by the degree constraint. All of the neighbors of v_0 have to be in P, otherwise P could be extended. Therefore v_0 has at least k neighbors in P. Let j be the maximum index of a neighbor of v_0. By the previous statement we have that j \ge k. Thus we ... 1 let G have more than 1 component. Suppose x,y are in different components in G. then (x,y) exists in \overline G. Suppose x,y are in the same component of G. Then there is a z in another component of G so that (x,z) and (z,y) exist in \overline{G}. Making (x,z),(z,y) a path from x to y. 1 We use induction on the length of the walk. Let W be a walk between u and v. Base step: if |W| = 1, then W is just the edge uv and it is a u-v path. Induction step: Now assume the statement is true for all u-v walks of smaller size than W.If all the vertices of in W are distinct, then W is u-v path and we are done. Otherwise, W ... 0 Hint: A walk is an edge sequence. But still can be written down as a sequence of vertices. Suppose there are repeating vertices in this sequence. Say u is such a repeating vertex. Delete all other terms in the sequence till the last occurrence of u in your walk. Do this for all repeating vertices and you will have yourself a path. I can't see a way ... 0 It's not really clear what you want. If it's just a list of graphs then: (a) Paths. (b) Cayley graphs for abelian groups. (c) Strongly regular graphs. There are other classes, but these would be the simplest. 2 This is just a humble suggestion.$$L(G) \; \text{is Eulerian} \iff \text {Each vertex in $L(G)$ has even degree} $$This will be true if and only if every edge in G is adjacent to an even number of other edges. Considering vertices incident to each edge in G, this condition will be satisfied if for each pair of adjacent vertices  u, v  in V(G), ... 3 For a graph G, a subgraph H of G, and a vertex v in H, let \deg_H(v) denote the degree of v in H. For a positive integer n and \delta\in\{0,1\}, let P(n,\delta) denote the statement "any (simple) graph on 2n+\delta vertices and exactly n(n+\delta)+1 edges has at least n triangles." As Aryabhata's answer in your link indicated, ... 4 There are unsolvable puzzles. Untangle gives you a graph, i.e. a set of vertices (points) with edges (lines) between some of them. You are asked to find an embedding of the graph into the two-dimensional plane such that no two edges cross each other. A graph where that is possible is called a planar graph. Not all graphs are planar - the smallest non-planar ... 1 I'm not aware of any established notation for this, however, the notion of incidence is usually understood in a more general sense, that is, not only with regard to vertices/edges, but whole sets. Therefore, you could say that$$\{(u,v) \in E \mid u∈W \lor v∈W\} \text{ is the subset of edges incident to }W. Also, there is another similar notion, namely, ...

2

With $n$ labelled vertices, there are $\dfrac{n(n-1)}{2}$ potential edges, each one of which may be present or not, so there are $2^{n(n-1)/2}$ possible different graphs.

Top 50 recent answers are included