# Tag Info

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 ...

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 ...

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 ...

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, ...

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), ... 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 ... 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 ... 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 ! 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 ... 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 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 "$\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 ... 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$... 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 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 ... 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 ... 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, ... 1 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 ... 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. ...

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