Tag Info

Hot answers tagged

7

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


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


3

Disclaimer: This is a simplified proof from Nancy Eaton's On Two Short Proofs About List Coloring Graphs . It's rather simple, but I was unable to form hints in a way that would make the intention clear, so I present all the details. As this is homework, please make an additional effort to rework the proof again, only by yourself. Also, should you need to ...


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


2

This is the type of result that's much easier to intuit than it is to rigorously prove. For a rigorous proof, it's probably best to enumerate the vertices and edges of each graph: Let $G_1$ and $G_2$ be cycles with: $$V(G_1)=\{u_1, u_2, \dots, u_{m}\}$$ $$E(G_1) = \{u_1 u_2, u_2 u_3, \dots, u_{m-1} u_{m}, u_{m} u_1\}$$ $$V(G_2)=\{v_1, v_2, \dots, ...


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


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


2

$1$ is an eigenvalue of multiplicity $1$ of a stochastic matrix as long as your graph edges give a path between every pair of vertices $(v,w)$,and the matrix summation will not converge if $1$ is an eigenvalue. Actually, the matrix summation wouldn't converge for any stochastic matrix. You can see this by noting that every power of a stochastic matrix is ...


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


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


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


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


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


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


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


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


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

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


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


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

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


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


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



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