# Tag Info

0

Exactly, because the infinite face touches both sides of the edges it has degree $4$. Since these edges are bridges we must count them twice, once for each side. Planar graphs have the property that if $n\geq3$, then $2m\geq3f$.

0

A simple graph is a graph that does not contain any loops or parallel edges. So, the vertex $u$ is not adjacent to itself and if the vertex $u$ is adjacent to the vertex $v$, then there exists only one edge $uv$. A complete graph of order $n$ is a simple graph where every vertex has degree $n-1$. In other words, every vertex in a complete graph is adjacent ...

2

The linked-to notes were maybe a little unclear on this point, perhaps in the interest of not being too pedantic. Anyway, for a given face $F$ of a connected plane graph, a boundary walk of $F$ is a closed walk that contains every edge on the boundary of $F$. This means that a boundary walk must start and stop at the same vertex. The degree of a face is ...

4

Every complete graph is also a simple graph. However, between any two distinct vertices of a complete graph, there is always exactly one edge; between any two distinct vertices of a simple graph, there is always at most one edge.

1

You'ra on the right track. Every edge of the dual is corssed by an edge of $G$, hence a cycle of length $k$ in the dual graph gives us $k$ edges of $G$ with one endpoint in the interior and one endpoint in the exterior of the cycle. Thus removing theses $k$ edges from $G$, we obtain a nonempty interior and a non empty exterior component of $G$ (or maybe even ...

0

Let $v_1=\{\}$, $v_2=\{a\}$, $v_3=\{b\}$, $v_4=\{c\}$, $v_5=\{a,b\}$, $v_6=\{a,c\}$, $v_7=\{b,c\}$ and $v_8=\{a,b,c\}$. We see that two vertices are adjacent if and only if their subsets differ by exactly one element. That is, if the symmetric difference of any two sets contains only one element, then they are adjacent. Thus $v_1$ is adjacent to ...

0

If $uv\notin E(G)$, then $uv\in E(\bar{G})$. Thus $d_{\bar G}(u,v)=1$. If $uv\in E(G)$, then $uv\notin E(\bar{G})$. This implies that there exists $w\in V(\bar{G})$ such that $uw\in E(\bar{G})$ and $wv\in E(\bar{G})$. So there exists a $u-v$ path of length $2$ in $\bar{G}$. Thus $d_{\bar G}(u,v)=2$ and it follows that $diam(\bar{G})\leq2$.

0

Start by listing out the possible subsets of $\{a, b, c\}$. So an example of three vertices are $v_{1} = \{a\}$, $v_{2} = \{a, c\}$, $v_{3} = \{c\}$. The vertices $v_{1}, v_{2}$ are adjacent, because they differ by one element. The same stands for vertices $v_{2}$ and $v_{3}$. However, $v_{1}$ and $v_{3}$ are not adjacent, as $v_{1}$ does not have a $c$ and ...

1

A maximum flow is a flow that attains the highest flow value possible for the given network. A maximal flow is a flow whose value cannot be increased without decreasing the flow along some arc. All maximum flows are maximal flows. Not all maximal flows are maximum flows. Figure 3.9 in the Bang-Jensen and Gutin textbook, first edition illustrates an ...

6

First hint: In a bipartite graph, the sum of the degrees on one side is equal to the sum of the degrees on the other side (each sum being equal to the number of edges). Can you split those numbers into two groups with equal sums? Second hint: Just one of the numbers is not divisible by $3$. That is, modulo $3$, you've got eleven $0$s and a $2$.

1

So, I can see one way to model this using a hypergraph. I have very little working knowledge in optimisation-type problems, so I don't know if this model will help: I'm hoping that someone else will give a better answer at some point. We have a set of transmitter-receiver pairs, each pair endowed with coefficients $i_m$, $\kappa_m$, where $i_m$ is the ...

0

You can view both $T$ and $T'$ as rooted trees by designating a vertex as the root arbitrarily. Define $r$ and $r'$ as the respective roots of $T$ and $T'$. We now work with these rooted viewings, which define an ancestor/descendant relationship between the vertices. For some $v \in V \cup V'$, choose an ordering of the children of $v$ and denote the ...

1

Claim: Let $G$ be a $k$-regular graph. Then $G$ has a 1-factorization iff $G$ has a edge $k$-coloring. Pf. => Let $F$ be a 1-factorization of $G$. For each perfect matching $M$ in $F$, assign to the edges in $M$ a distinct color $c_M$. Clearly this is an edge $k$-coloring of $G$. <= Let $C$ be an edge $k$-coloring of $G$. For each color $c$ assigned by ...

0

This is not possible. For some pair $u,v$ the 'mapped distance' $d(f(u),f(v))$ must be minimal. This implies that you cannot find any $t$, adjacent or not, with $d(f(t),f(v))<d(f(u),f(v))$.

0

If the assumption that a proposition is false leads to a contradiction, then the assumption is incorrect and the proposition must be true. In the proof that every subgraph of a tree is a tree we are given that the graph is connected since it is a tree and trees are connected by definition. Thus using the property that trees are acyclic is the best approach ...

0

Here is a start for what you are looking for. The number of different carbon chains is the same as the number of non isomorphic trees.

0

An undirected graph is one in which edges have no orientation. The edge (a, b) is identical to the edge (b, a), i.e., they are not ordered pairs, but sets {u, v} (or 2-multisets) of vertices. The maximum number of edges in an undirected graph without a self-loop is n(n - 1)/2. So , 10 * 9 / 2 = 45 Source : http://en.wikipedia.org/wiki/Graph_(mathematics)

-1

Both terms refer to the same thing. In the Wikipedia article on the maximum flow problem both terms are used equivalently. There you can also find some references to scientific publications that use both terms.

2

Suppose you have 7 stars. A, B, and C form a nearly equilateral triangle; AB and BC have length 1, AC is a little longer, $1+\epsilon$. B, D, E, F, and G lie on a straight line, going away from AC; each is $1/2$ a unit away from the next. Starting at A, the closest is B, then D, E, F, G, and then you have to go back to C. That's total length $3+GC$, which ...

0

Since $G$ is a graph of order $n$ such that $\delta(G)\geq(n-1)/2$, then $G$ is connected. Also, for every graph $G$, $\lambda(G)\leq\delta(G)$. Assume that $\lambda(G)\lt\delta(G)$. Let $X$ be a minimum edge-cut of $G$ where $|X|=\lambda(G)$. Then $G-X$ is disconnected by definition. However, since $\lambda(G)\lt\delta(G)$ we know that $G-X$ is connected ...

1

If $G$ is $0$-regular, then every vertex in $G$ has degree $0$. Thus $\kappa(G)=0$ since removing zero vertices results in a disconnected graph. Also, $\lambda(G)=0$ since there exist no edges in $G$ because $G$ is $0$-regular. Therefore $\kappa(G)=\lambda(G)$.

2

$\kappa(G)$ is vertex connectivity. That means, if I remove $\kappa(G)$ vertices from $G$, then $G$ will be disconnected. This proof is rather trivial. Can you further disconnect the graph? Obviously, not so $\kappa(G) = 0$. If $\lambda(G)$ is edge-connectivity, the proof is identical. Then combinatorially, $\kappa(G) = \lambda(G)$.

1

Let $C = \{v_{1}, ..., v_{k} \}$ be a vertex cover. By definition of a vertex cover, every edge is incident to some vertex in $C$. Suppose $C$ contains no minimum vertex cover. So begin removing vertices inductively. Since there is no minimum vertex cover, we can keep removing vertices from $C$ in this manner. The process will terminate since $C$ is finite. ...

1

It is, in fact, not planar. Here is a subgraph that is a subdivision of $K_{3,3}$. I colored the degree 3 vertices red to (hopefully) make it easier to see.

1

We will show that if T is not a tree, then there is an integer $k>0$ such as $p^{k}(y)=y$ for a $y \in T$. This doesn't agree with your definition. You want to show that there is no periodic point. By definition, a tree is acyclic. So it suffices to show that $p$ will end up traversing a cycle. That's how you should go about contrapositive. ...

0

If you have a simple graph, then the extremal case is a complete graph. In which case, there is an edge between each vertex, so there are $\binom{n}{2}$ such edges at most.

0

Here is a link describing the bipartite matching algorithm, including a worked out example. http://www.dreamincode.net/forums/topic/304719-data-structures-graph-theory-bipartite-matching/

1

Maximal independent sets are not unique. Consider $Q_{3}$, the hypercube on $8$ vertices. I can select two non-adjacent vertices and up to four non-adjacent vertices depending on my selection. Each such selection is a maximal independent set. The Wikipedia page has a really nice graphic demonstrating this: ...

0

For the isomorphisms on the second graph, we start by choosing the first edge, the tail of the graph. There are $\binom{5}{1} = 5$ ways of choosing this edge. We then choose an endpoint of that edge to be incident to the square. There are $\binom{2}{1} = 2$ ways of doing that. Then we choose the square in $\binom{4}{2}$ ways. That gives us $60$. The two ...

1

Look up http://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm Hopcropt-Karp algorithm for what I believe is a currently best-known solution (in terms of running time) except in very dense graphs.

0

If $G$ is k-regular, then the diameter is $log_{k}(n)$. So with a maximum degree, we get a lower bound as to the diameter using the same approximation: $diam(G) \geq log_{x}(n)$.

1

There are five. One has a root and one child on each side, the others have a root and all descendants to one side. The descendants to each side can form a line or an angle.

1

There is the identity automorphism, and then the reflection automorphism. The reflection swaps $b$ and $d$. Those are the only two automorphisms.

0

Each vertex in $n_{i}$ has degree $\sum_{j=1, j \neq i}^{n} |n_{j}|$, as each vertex in $n_{i}$ is incident to every vertex in the other partitions. There are $|n_{i}|$ vertices in $n_{i}$, so that's why we multiply out. So by the handshake lemma, we get: $$\sum_{i=1}^{n} (|n_{i}| * \sum_{j=1, j \neq i}^{n} |n_{j}|) = 2E$$

1

To get the number of graphs for the second graph, we start by choosing a triangle. There are $\binom{5}{3} = 10$ ways to do this. We then choose two of those vertices for to be adjacent to $c$ and $e$. There are $\binom{3}{2} = 3$ ways to do this. Then we choose $c$ and $e$, and there are two ways to do this. So by rule of product, $10 * 3 * 2 = 60$.

1

An automorphism is an isomorphism from a graph to itself. There can only be one possible mapping for $a \in V(G)$, and that is to itself. Now, $b, c$ are adjacent to each other. So we can swap their ordering, as they are both distance $1$ from $a$; and they are both distance $2$ from the other graph. Similarly, we can map $d, e$ in two possible ways. So we ...

3

Yes, see Robertson-Seymour theorem. Additionally The complete set of forbidden minors for toroidal graphs remains unknown, but contains at least 16000 graphs.

1

This solution is probably much longer than needed, the inequalities I am using might be improved on... The inequality $\lambda(G) \leq \delta(G)$ is well known and trivial. Assume now by contradiction that $$\lambda(G) < \delta(G) \,.$$ This means that we can disconnect the graph by removing $\delta(G)-1$ edges, lets call them $v_1,..,v_k$ where ...

1

Well, the Barabási-Albert model appears in context of social networks, neural networks and power grids. It is good because it reflects some properties that theses networks have, like the degree distribution is a power law. You can see this on the paper of Barabási and Albert: Emergence of Scaling in random Networks If you want something more recent, the ...

0

Henning's hint is really spot-on. There are no directed cycles. So this is a DAG. Now where does the graph "start"? It starts at node (1), correct? So updating the number of paths follows a recursive definition? How many paths of length one are there from node (1)? Count up the adjacencies. Now count paths of length (2). To do this, how many adjacencies do ...

1

Is it specifically a DAG? If so, process nodes in topological order, keeping count of how many different paths end at each node.

0

The number of closed walks of length $k$ in a graph is given by $tr(A^{k})$, where $tr$ represents the trace of the matrix (in this case, the adjacency matrix is $A$). Consider $tr(A) = 0$, as $K_{r, s}$ is a simple graph. So we have no loops. Now let's diagonalize $A = QDQ^{-1}$, where $Q$ is the eigenbasis matrix and $D$ is the diagonal eigenvalue matrix. ...

2

This is not true. A $k$-regular graph $G$ with $n$ vertices, where $n$ is odd has $\chi'(G) = k+1$. Consider an edge coloring of $G$ with $c$ colors. Each color can be assigned to at most $\frac{n-1}{2}$ edges, since no edges of the same color are incident with a common vertex. So: $$|E(G)| = \frac{kn}{2} \leq \frac{c(n-1)}{2}$$ $$\Rightarrow c \geq ... 2 The graph has 16 vertices, so any spanning tree will have 15 edges. The graph starts with 20 edges, so we need to remove 5. We have to break each of the four 5-cycles, so by the pigeonhole principle we will take a single edge from three of the 5-cycles and two edges from one of them. We also have to break the 4-cycle in the middle. If we remove an edge ... 1 Hint: A 2-regular graph is a disjoint union of cycles. From there it should be fairly easy to see there are only 2 simple 2-regular graphs on 7 vertices. 0 But why would a problem not be in polynomial time, when you cant solve for an input n? Note as well that if a problem is NP-Complete and we assume no polynomial time algorithm to solve it, we are assuming P \neq NP. While no proof showing P \neq NP, that tends to be what people believe. I think it's also important to put out some ... 2 Hint: Create G' as follows: For any w \in V create two vertices w_\text{in} and w_\text{out}. Connect them with an edge of zero cost. For any e \in E create two vertices e_\text{in} and e_\text{out}. Connect them with an edge of zero cost. For any e = (w \to w') \in E add edges \{w_\text{out},e_\text{in}\} and \{e_\text{out}, ... 4 The Fool's Method: T_n is an strongly regular graph with parameters ({n\choose 2}, 2(n-2),n-2,2), so its eigenvalues are 2(n-2) (with multiplicity 1), n-4 (with multiplicity n-1) and -2 (with multiplicity \frac{n(n-3)}{2}). So the number of triangles is one sixth of$$tr(A^3) = 8(n-2)^3+(n-4)^3(n-1)-4n(n-3). The KISS Method: Triangles in ...

2

Let $X$ be the graph of an $n\times n$ Latin square. The vertices of $X$ are the $n^2$ positions in the square, two positions are adjacenct if they are in the same row, or in the same column, or contain the same entry. This graph is regular with valency $3n-3$, in fact it is strongly regular and so it is known that its eigenvalues are $3n-3$, $n-3$ and $-3$. ...

1

I am not sure why a property such as vertex transitive may result in such a constant, perhaps you can explain your intuition. My suggestion here does not require such an assumption but may be helpful. I believe the matrix $M$ is somehow related to the adjacency matrix, so I will assume it is simply $A$. Notice that, the all ones vector, which is an ...

Top 50 recent answers are included