Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [graph-theory]

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.

0
votes
0answers
4 views

Proof of a Corollary to Hall's Marriage Theorem

I'm trying to prove Corollary 3.3 from this paper (http://www.sfu.ca/~mdevos/notes/graph/345_matchings.pdf) and am lost at the step that says: "Similarly, every vertex in N(X) has degree k, so t is ...
0
votes
0answers
21 views

Suppose that R(s, t − 1) and R(s − 1, t) are both even numbers..

Suppose that R(s, t − 1) and R(s − 1, t) are both even numbers. Prove that R(s, t) ≤ R(s, t − 1) + R(s − 1, t) − 1. I'm trying to learn proofs for graph theory and Ramsey theory but i'm strugging to ...
0
votes
1answer
19 views

Termination of The Ford-Fulkerson Algorithm

I am trying to do Exercises 7.2.3 in the book Graph Theory by Bondy and Murty, which wants the reader to prove that the Ford-Fulkerson Algorithm terminates whenever all capacities are rational. In ...
0
votes
2answers
15 views

Show that any RB-edge coloring of K3,3 contains a monochromatic path of length 3.S [on hold]

I'm trying to learn proofs using Ramsey's theorem but I'm getting stuck while attempting to solve this.. Any help would be greatly appreciated..
3
votes
3answers
74 views

Show that, in a group of n people, everyone has the same number of friends if..

Question: Consider a group of n people with the following properties: • no person is friends with everyone, • any pair of strangers share exactly one friend in common, • no three people are ...
0
votes
1answer
14 views

What is the normalized graph matrix if the row-sum of proximity matrix is zero?

Let $S \in \mathbb{R}_{\ge 0}^{n \times n}$ be the proximity (or similarity) matrix of a graph, e.g. $$ S = \left[ \begin{matrix} 0 & 0.9 & 0.3 \\ 0.9 & 0 & 0.4 \\ 0.3 & 0.4 & ...
0
votes
0answers
23 views

Graph factorisation

I have a graph having 6 vertices and its presentation is $E_{12}^4E_{13}^5E_{14}^6E_{24}^9E_{25}^2E_{35}^9E_{36}L_5^4L_6^{14}$. This means that there are $4$ edges connecting the vertices $1$ and $2$, ...
0
votes
0answers
10 views

Lower bound of number of independent sets

Let $G$ be a connected regular graph with even number of vertices $v$. Also let $i_{v/2}(G)$ be the number of independent sets of $G$ of size $\frac{v}{2}$. Is it possible that $i_{v/2}(G)> 2^{v/2}$...
1
vote
0answers
24 views

Random Graphs - Planarity

If I take a Random planar graph with $V$ vertices and $E$ edges, I would like to know the probability that it remains planar if I add in another random edge, I realise that there is probably no simple ...
1
vote
1answer
25 views

“Adding a linear number of vertices and edges”

Apologies for if this is a rather silly question, but the impetus for this question comes from the curious usage of the titular phrase within this conference paper right after the section entitled "2 ...
0
votes
2answers
27 views

there exists a bipartite graph whose size $\geq \frac{m}{2}$

The question I am trying to solve now is "Prove that every graph $G$ has a bipartite subgraph of size $\geq \frac{m}{2}$" by using a probability method (defining a sample space and a random variable). ...
0
votes
1answer
30 views

Determining Graph Automorphisms by Determining Ways of Permuting Edges

Here is an example from the book Groups, Graphs, and Trees (Ignore example 1.15; I accidently included it in my snippet of the pdf): From my understanding, the symmetry group of a graph $\Gamma$ ...
0
votes
0answers
12 views

Proof of equivalence of S-TSP solution with TSP solution (metric instances)

I am wondering where could I find proof for following S-TSP to TSP transformation. S-TSP (Steiner Travelling Salesman Problem) def: Let $G=(V, E)$ be a non-directed weighted graph. Let $V' \subset V$ ...
0
votes
1answer
22 views

Characterization of Strongly Regular Graphs

I am looking for a reference in which I can find a proof of the following result. A strongly regular graph is disconnected if and only if it is a disjoint union of complete graphs $K_n$ of the same ...
1
vote
1answer
26 views

Prove G is non-planar by contradiction

$G=(V,E). |V| = 25; |E| = 50.$ For every vertex $v \in V$, the degree of that vertex $d(v)=4.$ I am given that the shortest cycles in $G$ are 4-cycles (i.e. with 4 vertices). For a contradiction I ...
0
votes
0answers
28 views

Why is normalisation of a Laplacian matrix defined as $L - I$?

I have a piece of code that computes the Laplacian matrix using $I - D^{-\frac{1}{2}} A D^{-\frac{1}{2}}$, that is, it computes the symmetric normalised Laplacian. This Laplacian is not defined when $...
0
votes
0answers
71 views

Hall's Theorem for infinite graphs (Compactness theorem)

To Proof: Let $G = (V,E)$ be an infinite bipartite graph with $V = S \overset{.}{\cup}T$ and finite node degree for each node. G has a matching, that covers a set S iff for all subset $H \subseteq ...
1
vote
0answers
22 views

Real world application of finding all simple paths on a graph

I am currently designing a general purpose graph database. Recently I have started to consider supporting the "find all simple paths between two nodes" operation on the graph. However while there are ...
0
votes
0answers
13 views

Can cycle in a graph (not simple cycle for which edge and vertices cannot be repeated) have repeated edges?

The Data Structures book by Goodrich and Tamassia is saying, A path is a sequence of alternating vertices and edges that starts at a vertex and ends at a vertex such that each edge is incident to its ...
1
vote
0answers
31 views

the number of the longest paths of a complete undirected graph $K_n$

I am trying to find the number of the longest paths of a complete undirected graph $K_n$. My guess is $\frac{n!}{2}$. Any longest path in $K_n$ should have $n$ vertices. And given one longest path $...
1
vote
1answer
18 views

$m$-Trees are Infinite.

Let $\Gamma$ be a tree, and $m \ge 2$. If $\Gamma$ is an $m$-tree (all vertices have valence of $m$), then $\Gamma$ is infinite. My idea is to prove it by contradiction. Suppose that $\Gamma$ is ...
-1
votes
0answers
17 views

The Expected Value of a Random Graph [on hold]

My question is as follows: Proof that the expected value of a graph with $n $ Vertices is equal to $(n - 1)p$ $E[D] = (n-1)P $ $D$ = Random Variable
0
votes
0answers
13 views

Forbidden $K_4$ in a subgraph of $K_{10}(n)$

In terms of $n\geq 1$, find the maximum possible number of edges in a subgraph $H$ of $K_{10}(n)$, the complete $10$-partite graph with $n$ vertices in each class, containing no copy of $K_4$. It is ...
0
votes
0answers
15 views

collection of cliques

Let $G$ be a graph on $n$ vertices and let $C$ be a collection of cliques whose union is $G$. Let $\kappa = \min \{\sum_{c \in C}|V(c)| : \cup_{c \in C}$ $c = G\}$ ($C$ is a minimal collection). Show $...
0
votes
0answers
6 views

Reference request: general Turan density upper bounds

One problem I have encountered while doing research is that I find it difficult to find papers that were published decades ago. In particular, I am interested in "Extension of a theorem of Moon and ...
-1
votes
0answers
27 views

Draw a possible graph representing the acquaintances in this group of five people. [on hold]

There are five passengers travelling in a railway compartment. One passenger knows four of the others, there are three who know three fellow passengers each, and there is one who knows only one other ...
0
votes
3answers
32 views

Points in the Fano plane

Problem: Show that any two points in Fano plane are not contained in exactly two lines of the plane and their sum is contained in those two lines in which $p$ and $q$ are not contained. My attempt: ...
0
votes
0answers
28 views

Equivalent Characterizations of Trees

First some definitions: An edge path, or more simply a path, in a graph consists of an alternating sequence of vertices and edges $\{v_0,e_1,v_1,...,v_{n-1},e_n,v_n\}$ where $Ends(e_i) = \{v_{i-1},...
-1
votes
0answers
10 views

d regular bipartite graph independent sets

Given d-regular and bipartite graph G, show that the number of maximal independent sets is $< 2^{(1+o(1))n/4}$, where $n = |V(G)|$
0
votes
0answers
19 views

Quantity of Hamiltonian cycles

If I have four vertices, each of which are adjacent to two others, how are the Hamiltonian circuits for those vertices typically counted? If I envision the unit circle of the real plane’s axis ...
0
votes
1answer
59 views

Induction question about partitioning with a condition

We have $n$ students which are in $k$ classes. We know that between each two classes, there exist two persons A and B who know each other. Prove that we can put students in $n-k+1$ groups such that ...
0
votes
1answer
25 views

Are Euler trails and tours of a graph the same as Hamilton paths and cycles of the corresponding “edge graph”?

Is knowing information about Euler paths and Euler tours about a graph $G$ the same as knowing information about Hamilton paths and cycles of the graph $H$ obtained from $G$ such that vertices of $H$ ...
0
votes
0answers
17 views

Find a matrix that describes a modularity score of a partition.

For a partition P of a network of n nodes and m edges into two disjoint communities, $V_{1}$ and $V_{2}$. Let $s=[s_{1},s_{2},...,s_{n}]$ where each $s_{i}$, corresponding to each vertex is 1 if that ...
0
votes
1answer
13 views

Number of all possible sub-trees of m nodes of a given k-regular tree of n nodes.

I have a k-regular tree of n nodes rooted at u and I wish to find all its possible sub-trees of m nodes, again rooted at u. It will be of immense help. Thank you.
1
vote
1answer
27 views

Can we decompose any connected Regular graph (or subclass of it) into Hamiltonian cycles and Perfect matchings?

I need to decompose any connected Regular graph into Hamiltonian cycles and Perfect matchings. Is there any theorem that guarantees this or is there any counter example to this ? If there is such ...
0
votes
2answers
44 views

How to prove there are unreachable states in this bit flipping algorithm only for lengths $n=3k+2$?

This is similar to Bit flipping algorithm, but the algorithm is a little different. Specifically, we have bit string of length $n$, and we can choose any bit to flip and then we flip also the two ...
0
votes
2answers
51 views

For what n,m the following conditon hold

Suppose their are n people and each person is friend with exactly m other people . What should be the relation between n and m for the following condition to hold and how to prove that . For example ...
0
votes
0answers
15 views

Visualizing a 2-torus on a planar shape using periodic boundary conditions

A torus can be represented by a square with periodic boundary conditions, which makes it easy to draw embeddings of graphs on the torus using a piece of paper. Is there a similar mapping of the 2-...
-1
votes
0answers
21 views

Give edge set of graph with vertex set {a.b,c}

I am trying to understand if I am thinking about this questions correctly. For each of the following, either give the edge set of a graph on vertex set {a,b,c} that has the stated degree sequence, or ...
0
votes
0answers
15 views

Prove that split graphs are perfect graph [on hold]

Split graph are self complementary and I know that complement of a perfect graph is also a perfect graph. But how to prove this thing?
1
vote
0answers
23 views

Graph theory - number of spanning trees generalisation [duplicate]

I'm trying to generalise the number of spanning trees of a complete graph after deletion of any edge. That is, I'm trying to find $$ \tau (K_n - e)$$ For $n$ number of vertices and we are deleting one ...
1
vote
0answers
23 views

Removing edges from a digraph to obtain the smallest digraph

Say that I have a connected digraph D composed by N nodes and E edges, and a root node ...
0
votes
1answer
11 views

Examples to show that the edge-bound for no paths of length $k$ is best

Let $G$ be an $n$-vertex graph containing no path of length $k$. One can show (not that easy but doable) that $e(G) \leq \frac{k-1}{2}n$ (equivalently, the average degree $\bar{d}$ satisfies $\bar{d} \...
0
votes
1answer
20 views

Recursive formula for the definition of tree-depth of a graph

I am trying to understand the recursive formula for defining tree-depth as suggested in Sparsity by Nešetřil, Jaroslav, Ossona de Mendez, Patrice. I am trying to implement in python but I am slightly ...
3
votes
1answer
35 views

Generalization of graph connectivity to edge cases (null graph, singleton graph)

I am looking for advice on what would be a reasonable or useful generalization of vertex- and edge-connectivity to the graphs with 0 and 1 vertices (null graph and singleton graph). Motivation: ...
2
votes
0answers
41 views

Assigning people to jobs

We have $n$ people and $n$ jobs. Assume that each person is able to do $k$ jobs $0<k<n$ and each job can be done by $k$ people. Proof that each job can be done at the same time My try Ok, I ...
0
votes
0answers
11 views

In which case the adjacency matrix of a directed graph will be symmetrical across the diagonal?

Can some body explain which scenario we will get the adjacency matrix of a directed graph symmetrical across the diagonal
1
vote
1answer
57 views

Is there a way to classify all power-invariant graphs?

Suppose $G = (V, E)$ is a finite undirected simple graph. Let’s, define the $n$-th power of a graph (where $n \in \mathbb{N}$) as graph $G^n = (V, E_n)$, where $$E_n = \begin{cases} E & \quad n = ...
1
vote
0answers
36 views

How many nodes are there of each degree?

Q:A graph has 12 edges and 6 nodes, each of which has degree of 2 or 5. How many nodes are there of each degree? let m = the amount of edges, then $$ 2m = \sum_{v\in V} deg(V) $$ from here we can ...
2
votes
1answer
31 views

Prove that two graphs are isomorphic

I just found an old book about number theory and graph theory I used on my first course at university many years ago. Looking inside it, I found a handwritten note pointing to a problem that says: ...