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

3
votes
0answers
38 views

Proving a graph has a property if all finite subgraphs have that property

Given a graph $G=(V,E)$ and an integer $k\in\mathbb N$, we will say that $G$ is $k$-good if: for every division $V=\bigcup_{i\in I} U_i$ such that $i\not=j \Rightarrow U_i\cap U_j =\emptyset$ and ...
0
votes
0answers
38 views

Min. Spanning Tree - Same weight

Prove that every minimum spanning tree of a connected graph, $G$, has the same maximum edge. Intuitively, this makes sense to me. You need to have that heavy edge because that is the cheapest ...
2
votes
1answer
24 views

Definition of compatible vertices

I'm reading the Extremal Graph Theory book by Bollobás, and I'm stuck at the definition of 'compatible vertices'. It's here at the bottom of p.13 It says : "Call two vertices compatible if every ...
0
votes
0answers
37 views

How to reduce a graph via decomposition?

Is there a Java / C# library that can be used to reduce a graph via decomposition? Or could someone point me to a good tutorial where I can learn all these? E.g.
2
votes
0answers
25 views

Graph planarity and electronic circuit boards

In another MSE question, I found the following definition for 2-layer circuit board decomposition of a graph: A circuit board is defined as a pair of planar graphs with vertices identified, i.e. ...
0
votes
2answers
43 views

Tree with $k$ edges is a subgraph of any graph with all vertices of degree $\geq k$.

Let $T$ be a tree with $k$ edges. Let $G$ be a graph where every vertex has a degree of at least $k$. Show that $T$ is a subgraph $G$. I know this implies that in a graph where every vertex is at ...
1
vote
1answer
39 views

Interactions between geometry and graph theory.

I'm looking for some nice theories or just exercises, with both geometrical aspects and graph theoretics aspects. Example may include for instance the 4-color theorem or Euler characteristics, maybe ...
1
vote
1answer
43 views

Examples of Matroids

Preparing an exam, I'm looking for examples of matroids and maybe hints or references on proves that they are. (what I already know are representable matroids and graphic matroids)
4
votes
1answer
38 views

Chromatic number of generalized hypercube

It's clear that the chromatic number of $Q_n$ is $2$. But what about the graph $G$ with vertex set ${n}^{(r)}$ where two vertices are adjacent if and only if their coordiantes differ by one? Can't ...
2
votes
1answer
51 views

How to call a tree with a single branch?

How do you call a tree with only one branch (in other words, where every vertex has maximum one direct successor)?
3
votes
0answers
74 views

Minimal number of edges removed to make a graph triangle free

I'm interested in finding an upper bound on the expected value of the minimal number of edges one needs to remove from a random graph $G_{n,p}$ (where each edge appears with probability $p$) in order ...
1
vote
1answer
21 views

Relation between a complete k-partite graph and a perfect graph

Is a complete $k$-partite graph also a perfect graph? I know that the result holds for bipartite graphs. Can we claim the same for higher order partitions?
1
vote
1answer
27 views

Irreducible matrix equivalent connectedness of matrix graph?

If a matrix is irreducible, based on the following definition A matrix is reducible if there are two disjoint sets of indexes $I,J$ with $|I|=\mu$, $|J|=\nu$, $\mu+\nu=n$ such that for every ...
2
votes
1answer
43 views

Checking connectivity of adjacency matrix

What do you think is the most efficient algorithm for checking whether a graph represented by an adjacency matrix is connected? In my case I'm also given the weights of each edge. There is another ...
0
votes
2answers
40 views

Graph Theory, with algorithms like kruskal and something more

The new government of the archipelago of Sealand has decided to join six islands by bridges to connect them directly. The cost of building a bridge depends on the distance between the islands. This ...
0
votes
1answer
24 views

Generators Trees in a Tree

My question is very short: How many spanning trees have a tree? Thanks in advance
1
vote
1answer
52 views

Stable Marriage - set of preferences such that every arrangement is stable?

This is a homework problem from the MIT OCW math for CS class, assignment 4, problem 5. Prove or disprove the following claim: for some n ≥ 3 (n boys and n girls, for a total of 2n people), there ...
0
votes
0answers
20 views

Hypergraph notation and hypergraph morphisms

There are two parts to my question. The first part is about notation for hypergraphs. The sconed is about the notion of morphisms for hypergraphs. For the notation part, the context is that I make ...
6
votes
1answer
47 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
52 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
25 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
87 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
94 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
45 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
34 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
19 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
69 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
10 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
28 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
77 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
27 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
44 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
44 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
18 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
44 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
37 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
29 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
34 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
22 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
63 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
49 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
33 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
34 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
43 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
44 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$ ...