Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

learn more… | top users | synonyms

6
votes
1answer
45 views

Does $K_{15,15}$ decompose into $K_{5,5}-C_{10}$ and $K_{5,5}-(C_6 \cup C_4)$ subgraphs?

Following on from this question: Q: Does $K_{15,15}$ decompose into $K_{5,5}-C_{10}$ and $K_{5,5}-(C_6 \cup C_4)$ subgraphs? or equivalently Q: Does there exist a $15 \times 15$ matrix ...
3
votes
1answer
15 views

Let $G$ be a loop-less undirected graph. Prove that the edges of $G$ can be directed so that no directed cycle is formed.

Can someone please verify my proof or offer suggestions for improvement? Let $G$ be a loop-less undirected graph. Prove that the edges of $G$ can be directed so that no directed cycle is formed. ...
1
vote
1answer
51 views

Film Festival, with intersections graphs

I encourage you to read this problem. I have a doubt, have films 1 and 2 the same type? I read the problem and I think that films {1,3,5}, {2,4,6}, {3,4} and {5,6} are grouped, but not is the case ...
1
vote
1answer
24 views

Draw a graphic only passing one time

I would like to know when I can draw a graph, without lifting the pencil and passing once for each edge? What theory is behind that? Thanks for your time
0
votes
1answer
34 views

Homomorphism from a commutative group?

I came across this question in a practice exercise and can't quite understand it. If f is a homomorphism from a commutative group $(S,*)$ to another group $(T,*')$, then prove that $(T,*') is also ...
3
votes
1answer
84 views

A graph on the cities of a country

In some country several pairs of cities are connected by direct two-way flights. It is possible to go from any city to any other by a sequence of flights. The distance between two cities is ...
3
votes
1answer
72 views

Draw this shape - no double lines, no lifting pen? Impossible!?

I'm 99% sure this isn't possible! But... is there anyway to draw this shape without lifing the pen and without redrawing over any lines?! Thanks :-)
0
votes
1answer
44 views

Making a Graph having edges

V is the set of those two-letter words built over {w, x, y, z} whose first letter is y or z. The graph G = (V, A) is defined so that two words of V determine an edge of A if they differ in exactly one ...
2
votes
0answers
32 views

Proof of chromatic number of a graph

Let $G$ be graph, let $x\in V(G)$ with $|\delta_G(x)|=\Delta(G)$. For all other nodes $v\in V(G)\setminus\{x\}$ let $|\delta_G(x)|\lt\Delta(G)$. Furthermore assume we have $v_1,v_2,v_3\in V(G)$ ...
3
votes
0answers
17 views

Connected graph where edge costs depend on a parameter $t$. Find the $t^*$ which gives the minimum cost minimum spanning tree.

The set-up: Let $G=(\,V,\,E\,)$ be a connected graph. Associated with every edge $e\in E$ is a cost/weight function $f_e(t) = a_e t^2 + b_e t + c_e $, where $a_e>0$. For a fixed $t$ we can define ...
1
vote
0answers
66 views

Research Topics Needed

This coming academic year a professor has asked me to find some topics that I wish to pursue to write about. The problem/topic that will be discussed doesn't have to be open, but my trouble is that I ...
5
votes
2answers
92 views

Does $K_{12,12}$ decompose into $K_{4,4}-I$ subgraphs?

Q: Does the complete bipartite graph $K_{12,12}$ decompose into $K_{4,4}-I$ subgraphs, where $I$ is a $1$-factor (i.e., a perfect matching)? The obvious necessary conditions work: $K_{12,12}$ ...
0
votes
0answers
7 views

Poisson distributed graphs

I am currently reading a paper about poisson distributed graphs and came across the following formula. Apparently the degrees of the graph are distributed binomially through the following ...
0
votes
1answer
27 views

New way of combining information in graphs

So, I am working for a social project involving graph theory. I have a dynamic dataset (weighted and undirected), I made graphs out of them ( for 10 years ). Now, I am trying to find out relations ...
3
votes
1answer
67 views

Textbooks on graph theory

I've read the textbook Groups and Their Graphs by Grossman, and I'm interested in learning more about graphs. I know about O. Ore's book in the same series (Graphs and Their Uses), but I'm interested ...
1
vote
0answers
26 views

Round robin tournament scheduling with additional constraints

I'm looking for a solution to the following problem. Given $n = a\cdot (b-1) + 1$ players, $a$ and $b$ being integers with $a \leq b$, I want to schedule a round-robin tournament where every player ...
4
votes
1answer
42 views

All $k$-regular subgraphs of $K_{n,n}$ have a perfect matching: a proof without Hall's Marriage Theorem?

There are several ways of describing this result: Theorem: For $k \in \{1,2,\ldots,n\}$, any $k$-regular subgraph of $K_{n,n}$ has a perfect matching (also known as a $1$-factor). I tend to ...
1
vote
1answer
39 views

Partition Graph Challenging Question

I want to find in which of the following Graph, the edges cannot partitioned to triangles? Km,n,r means 3-Partite Complete Graph with m, n, and r sections. a) K7 b) K12 c) K3,3,3 d) K5,5,5 i ...
0
votes
1answer
14 views

Planner Combination Problem on Graph

I ran into a Graph Problem. Suppose G is A Planner Graph with 100 Vertices such that if connect each two Non-adjacent vertices, the resulting graph would be non-planner. what is the number of edges ...
1
vote
1answer
38 views

Perfect Matching Combination Problem

We know: A perfect matching (a.k.a. 1-factor) is a matching which matches all vertices of the graph. if we remove edges of perfect matching of a 12-Complete Graph. how many triangle remain in this ...
1
vote
2answers
36 views

graph theory: show that for k=4 hesse diagram is not a planar graph

In this picture you can see the hesse diagrem of $\subseteq$ over $P(\{x,y,z\})$ For the set $A$ with $k$ elements, $k>0$ look at the diagram as a graph, it's vertices are the members of $P(A)$ ...
0
votes
2answers
28 views

In a 2-connected simple graph, is there always a simple cycle containing any given path P and disjoint edge e?

For any finite simple graph $G$ which is 2-connected, given a path $P$ and a disjoint edge $e$, is it true that there is always a simple cycle containing $P$ and $e$? If instead of an edge $e$, a ...
1
vote
1answer
27 views

Convert adjacency matrix to graph

Is there any online service that can provide possible graphs (the simplest one) when I give a sequence of integers (node degrees) as input (or reject the input) -based on Erdős-Gallai formula? Thanks ...
0
votes
1answer
18 views

graph theory: the degree of vertices in an hesse diagrem graph

In this picture you can see the hesse diagrem of $\subseteq$ over $P(\{x,y,z\})$ For the set $A$ with $k$ elements, $k>0$ look at the diagram as a graph, it's vertices are the members of $P(A)$ ...
0
votes
1answer
20 views

graph vertex chromatic number in a union of 2 sub-graphs

$G_1$ is graph on the set of vertices $\{1,2,3,4,5,6,7,8\}$, $G_1$ vertice chromatic number is 5. $G_2$ is graph on the set of vertices $\{7,8,9,10,11,12,13,14,15,17,18,19,20\}$, $G_2$ vertice ...
0
votes
2answers
31 views

Number of spanning trees of a graph (behind the formula)

Given $G$ a subgraph of $K_n$ s.t. $G$ has $n$ vertices with adjacency matrix $A$; why is $$\sum_{T \text{ spanning tree of }K_n}\prod_{(i,j)\in T}A_{i,j}$$ the number of spanning trees? I can't get ...
1
vote
1answer
62 views

Graph with edge disjoint cycles

If the vertices of graph have a degree of at least $n\geq2$, show that the graph has at least $\frac{n}{2}$ edge disjoint cycles. Unsure how to approach this, but I understand that edge disjoint ...
2
votes
1answer
48 views

Connected bipartite graph

Let $G$ be a bipartite graph with $n$ vertices. Prove that if every vertex has degree at least $\frac{n}{4} + 1$, then $G$ is connected. I'm assuming that number of vertices in this bipartite graph ...
0
votes
1answer
30 views

How to compute a marginal probability

Given a weighted graph, using the Kirchhoff's matrix tree theorem, how can I compute the marginal edge presence probability: $$P_\beta(ij)=Z_\beta^{-1}\sum_{\text{T spanning tree:$(i,j)\in ...
1
vote
0answers
33 views

Strongly regular tournament

A digraph on $n$ vertices is called a tournament if there is a exactly one directed edge between any two distinct vertices. A vertex $v$ dominates a vertex $w$ if there is an edge from $v$ to $w$. ...
0
votes
2answers
41 views

Graph theory: graph coloring quesiton [duplicate]

$G_1$ is graph on the set of vertices $\{1,2,3,4,5,6,7,8\}$, $G_1$ vertice chromatic number is 5. $G_2$ is graph on the set of vertices $\{7,8,9,10,11,12,13,14,15,17,18,19,20\}$, $G_2$ vertice ...
1
vote
2answers
43 views

For all $1 \leq i < j \leq k$, the subtrees $T_i$ and $T_j$ have a vertex in common. Show that $T$ has a vertex which is in all of the $T_i$.

Can someone please verify my proof or offer suggestions for improvement? I am aware that there is a similar question elsewhere, but I want help with my proof in particular. Let $T_1, \ldots, T_k$ ...
0
votes
2answers
24 views

Prove that a sequence of positive integers $d_1, d_2, \ldots, d_n$ is a degree sequence of a tree if and only if $d_1+d_2+\ldots+d_n = 2(n-1)$ [duplicate]

Prove that a sequence of positive integers $d_1, d_2, \ldots, d_n$ is a degree sequence of a tree if and only if $d_1+d_2+\ldots+d_n = 2(n-1)$ $(\Rightarrow)$ This follows from the handshaking ...
1
vote
0answers
34 views

Find minimum cut corresponding to maximum flow

I am trying to find the minimum cut corresponding to the maximum flow that is given in the following network (the numbers in italic represent flow; the boldfaced numbers represent capacity). I tried ...
1
vote
0answers
22 views

A inequality on a graph and finding the best constant

Find the smallest positive constant $c$ satisfying: For any simple graph $G=G(V,E)$, if $|E|\geq c|V|$, then $G$ contains $2$ cycles with no common vertex, and one of them contains a chord. Note: The ...
2
votes
1answer
44 views

Proof completion: Determine a simple expression for $\tau(G)$ in terms of the vertex degrees of $G$. (details inside)

I need some help completing a proof I wrote (or seeing a simpler solution to the same problem). For a list of paths $P_1, \ldots , P_m$, let $L(P_1, \ldots, P_m)$ be the number of paths in $P_1, ...
2
votes
1answer
21 views

Prove that there is an edge $e' \in E(T')-E(T)$ such that $T'+e-e'$ and $T-e+e'$ are both spanning trees of $G$.

Can someone please verify my proof or offer suggestions for improvement? Let $T, T'$ be two spanning trees of a connected graph $G$. For $e \in E(T)-E(T')$, prove that there is an edge $e' \in ...
3
votes
0answers
47 views

What is the number of labeled caterpillars?

A caterpillar is a tree in which all the vertices are within a distance 1 of a central path. (See the Wikipedia article: Caterpillar tree, for an example and some equivalent characterizations). The ...
0
votes
1answer
28 views

Show that a finite regular bipartite graph has a perfect matching

Some preliminaries: A matching in a bipartite graph with vertex set $X \cup Y$ is a subset $E_1$ of the edge set such that no vertex is incident with more than one edge in $E_1$ A complete matching ...
0
votes
0answers
17 views

Threshold function for component of size $k$

Show that, for each fixed $k$, there is a function $p(n)$ such that the probability that $G(n,p(n))$ has a component of size exactly $k$ tends to $1$ as $n \rightarrow \infty$. My initial thoughts are ...
0
votes
1answer
48 views

what is the significance of the inverse of an adjacency matrix?

Suppose I have a graph and I calculate the eigenvalues of the adjacency matrix and find that there are some number of zero eigenvalues. Do zero eigenvalues have any significance? Also is there a good ...
0
votes
1answer
29 views

Why doesn't the Back and Forth Method for Infinite Random Grap use the Axiom of Choice?

A way to proof that any two Rado graphs (countably infinite nodes, has graph extension property) are isomorphic, is to use the back and forth method. At each step of the method, we have a vertex $v$ ...
1
vote
0answers
55 views

Set partitioning question

I have the following problem. I have $n$ sets $A_1$ to $A_n$ each with $k$ elements. Any two sets are disjoint. I'm looking to determine a second set of $m$ sets $B_1$ to $B_m$ such that: the sets ...
1
vote
0answers
35 views

Edge choosability(edge list coloring) of cycles

I have 2 cycles with 6 length as shown below. I want to show that the above graph is 4-edge-choosable. I don't know where to start. It's known that every cycle of even length is 2-edge-choosable, ...
1
vote
0answers
14 views

What, if any, is the name of a k-uniform hypergraph where edges are ordered tuples

Suppose I have a hypergraph where the set of vertices can be partitioned into n subsets with n < k, and edges in this graph are restricted to ordered tuples having some structure imposed relating ...
22
votes
1answer
385 views

Zombie outbreak on a $k$-regular graph

Suppose we have a zombie outbreak on a connected $k$-regular graph of order $n$. There are $n_0$ initially infected zombie nodes, and each turn, each zombie infects its neighbors with probability ...
3
votes
0answers
30 views

Diameter of undirected graph

Let $G$ be a strongly connected directed graph of diameter $D$, and suppose that we remove the orientation of the arcs, thus getting an undirected graph $G'$ with diameter $D'$. Obviously, $D' \leq ...
0
votes
0answers
37 views

How to show a total order is product order

Besides the definition of product order, is there any other way to show that a total order on two sets can induce a product order? Because I want to solve the problem below: For two graphs ...
1
vote
0answers
36 views

Variations of M,n,k-games

I just read about M,n,k-games and wondered if the following variation (with fixed $k$) has been studied as well and if there exists a name for it: Two players consecutively mark elements of ${\bf Z}$ ...
0
votes
1answer
15 views

Differnce between circuits in graphs

Given a full undirected graph with 3 vertices: $v1, v2, v3$ and $3$ edges. Is there any differnce between those 2 cycles: $C1: v1-{(e1)}-v2-{(e2)}-v3-{(e3)}-v1$ $C2: ...