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

1
vote
1answer
232 views

$\chi(G)+\chi(G')\leq n+1$

How to prove, that the sum of chromatic numbers of graph and it's complement is smaller then the number of vertices incremented by one? $\chi(G)+\chi(G')\leq n+1$ The notes from my classes say to ...
2
votes
1answer
81 views

Why do people not use “partially directed” graphs?

Are there structures in use which are a mix of directed and undirected graphs? I.e. the effective edge-set consists of both directed and undirected vertex pairs. In the case that the graph is simple, ...
1
vote
1answer
51 views

Need help with a lemma explanation regarding triangle counting in graphs

Can you please explain this lemma? I read it in this research paper.
0
votes
1answer
96 views

Edge chromatic number question (Graph theory)

If $G$ is a regular graph with an uneven number of vertices, prove that $\chi'(G) = \Delta(G) + 1$; where $\Delta(G)$ is the maximum degree (in this case any degree) of $G$ and $\chi'(G)$ is the ...
1
vote
2answers
104 views

Simple $2$-connected Graph with $\chi(G)=3$

I need to prove that for $G$, a simple $2$-connected graph with chromatic number $\chi(G)=3$, that every $v \in V(G)$ is contained in an odd cycle. Something tells me I need to somehow show that ...
0
votes
1answer
89 views

Subgroup lattice

I've been searching around for a while now and can't seem to find a clear explanation of what a subgroup lattice of a group actually is. I see the vertex set is given by the subgroups of the group, ...
2
votes
2answers
75 views

Number of spanning trees of $K_{3,3}$.

I want to know how many different spanning trees of $K_{3,3}$ are there. I know, that there's a nice formula that says, that it's $3^2*3^2$, but the proof of it is way beyond my scope, so I'll need ...
1
vote
0answers
69 views

Matchings in $G=(V,E)$ be an undirected graph, and let $S,T\subseteq V$ be two sets of vertices with no common neighbors

Let $G=(V,E)$ be an undirected graph, and let $S,T\subseteq V$ be two sets of vertices with no common neighbors (there can be edges between $S$ and $T$). We need to show that if there exists a ...
0
votes
1answer
770 views

What is the difference between a $k$-degenerate graph and a graph with max vertex degree $k$?

A $k$-degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most $k$. But a subgraph $H$ of a graph $G$ can be equal to the full graph $G$, therefore there will ...
1
vote
1answer
46 views

Determinants, traces and isomporphism of graphs

Question Prove that if A,B are adjacency matrices of two graphs, and their traces or determinants are not equal then the graphs are not isomorphic. Thoughts I know that 2 graph are isomorphic iff ...
1
vote
1answer
27 views

Lp graph theory

Let $X=X\left(V,E\right)$ be a graph. Let $f$ be a function on $X$. Let $1\leq p<\infty$. If we define $L^{p}\left(X\right)$ to be the set of all functions $f$ on $X$ such that ...
0
votes
2answers
152 views

What is the contrapositive of this theorem?

This theorem: A connected graph has a Euler path but no Euler cycle if and only if exactly two vertices have odd degree. Is it: If at least one vertex is of even degree, then the graph has no Euler ...
0
votes
1answer
94 views

Find number of perfect paths

Given N Vertices and M Edges. Each Edge connects two vertices. There is at most one way to move between each pair of vertices. Each vertex is either locked or unlocked .There is a perfect path ...
1
vote
1answer
62 views

Association between Hamiltonian and Eulerian graphs

I have a question, and also an answer which I assume, is correct, but would like to ask, if some of you could elaborate, and add validity to the provided claim or develop a discussion. I did not find ...
0
votes
1answer
23 views

How to identify a variable-sized zone by a point given by coordinate?

The Cartesian plane is partitioned into zones of variable sizes. A zone is always a rectangle. For example, a zone can be represented like $x \in (0, 3], y \in (30, 50]$ The range in the Cartesian ...
0
votes
1answer
54 views

Efficient algorithm for finding intervals in a DAG

Apologies if I don’t use the right terminology, I’m an outsider to the field. Also I'm not sure whether to post this here or in programmers.stackexchange as my aim is primarily to find an efficient ...
1
vote
1answer
1k views

Show that a regular, connected bipartite graph does not have a bridge.

I need to show, that a connected regular bipartite graph (degree of the graph is $>1$) does not have a bridge. Well let's assume that there is a bridge $e$. After we cut it, the graph is divided ...
1
vote
1answer
35 views

graph theory term for highway exit that if you miss will massively increase distance to destination?

usually when driving with GPS you can miss an exit, and GPS will recalculate another route with similar distance to destination. Perhaps it will make you turn around and go back. But, maybe after the ...
1
vote
0answers
51 views

pierre simon laplace and his knowledge of the (Laplacian) matrices

so as we all know, there is a graph matrix called the Laplacian that is used in some eigenvalue/eigenvector/graph theory/spectral theory problems. i'm wondering if the name of this matrix is ...
1
vote
2answers
2k views

How many different spanning trees of $Kn / e$ are there?

I need to know how many different spanning trees of $K_n / e$ are there. $K_n / e$ is a graph created by removing one of the edges of a full graph $K_n$. Well as we all know the number of spanning ...
4
votes
1answer
436 views

Combinatorial problem: Directed Acyclic Graph

How many unique landscapes exist in 5D DAG (directed acyclic graph)? There are $2^5$ points (eg: 00000, 00001, ... 11111) and $(2^5)!$ combinations. The problem is a combinatorial problem. It should ...
2
votes
1answer
139 views

Usefulness of eigenvalue centrality

Question for the network theorists/computer scientists: I heard that the eigenvalue centrality is "useless" and "too sensitive to jump behavior" for directed graphs. $\bullet$ What does this mean ...
1
vote
2answers
90 views

Even Degree Bridge Proof

Prove that every connected graph all of whose vertices have even degrees contains no bridges. Any help/hints are greatly appreciated.
3
votes
1answer
518 views

Show, that a symmetric difference of edge cuts is an edge cut.

I have two edge cuts $A,B$. An edge cut is a set of edges, whose removal from $G$ makes the graph disconnected (there exist some vertices $x,y$ such that there's no path connecting them). I need to ...
1
vote
1answer
34 views

Finding all “bad” triangles in a full-simple-graph

Let $G = \left\langle {V,E} \right\rangle$, a simple and complete graph with the size of $n$. Each edge in the graph can be colored with blue or red. A "bad" triangle defined to be a triangle ...
2
votes
1answer
88 views

Characterizations of Chromatic Polynomials

Can somebody help me to prove these? Let G be a nontrivial graph and $P(G,t)$ be the chromatic polynomial of G where $t$ is a nonnegative integer. If $G$ is connected, then $t$ ...
0
votes
2answers
176 views

Generating forests from a graph?

I'm unable to fully understand how a graph could have many forests. I understand that a forest is a graph that has no circuits. So basically what I understood is that we call a graph a forest if it is ...
3
votes
3answers
5k views

Difference between a tree and spanning tree?!

I'm unable to understand the difference between a tree and a spanning tree. A tree is a graph that is connected and contains no circuits. A spanning tree of a graph G is a tree that contains every ...
0
votes
1answer
38 views

Shared vertices in connected components in graphs?

I'm reading about graph theory, and especially a paper that mentions: spanning forests. Suppose I have two connected components of a graph, is it allowed that some vertices in the first connected ...
2
votes
0answers
108 views

Expected size of intersection in a scale-free directed graph

Let $W$ be the Wikipedia graph, in which every page $p_i$ is represented by a vertex $v_i$, and there is a directed edge between two vertices $v_i$ and $v_j$ if page $p_i$ links page $p_j$. This ...
0
votes
1answer
88 views

Let $G = (V,E)$ be a graph with $n$ vertices and let $\delta(G) = \min_{v\in V}\deg v$ prove the stmt…

a) if $\deg u + \deg v \ge n-1$ for every two non adjacent vertices $u$ and $v$ of $G$, then $G$ is connected. b)Prove that the bound in (a) is sharp by finding a disconnected graph on $n$ vertices ...
2
votes
2answers
197 views

Prove or disprove: involves Chromatic numbers, and subgraphs isomorphic to Kr

Prove or Disprove, a) if a graph $G$ contains a subgraph isomorphic to $K_r$, then the chromatic number is greater than or equal to $r$ b) if the chromatic number is great than or equal to $r$, then ...
0
votes
1answer
148 views

Proving the number of subgraphs of $G$ isomorphic to $F$

Let $F$ and $G$ be graphs. Let $sub(F, G)$ denotes the number of subgraphs of $G$ that are isomorphic to $F$, let $inj(F, G)$ denote the number of injective homomorphisms from $F$ to $G$ and let ...
0
votes
1answer
41 views

In a bipartite graph $G$ with bipartite sets $X$ and $Y$, prove that $\alpha'(G)=|X|-\max_{S \subset X}(|S|-|N(S)|) $

In a bipartite graph $G$ with bipartite sets $X$ and $Y$, prove that $\alpha'(G)=|X|-\max_{S \subset X}(|S|-|N(S)|) $ No idea how to approach this one...any leads please?
0
votes
1answer
127 views

Hamiltonian graph question

So I have this graph I am able to see that it is not Hamiltonian. However, I wish to use the following theorem : If $G$ is a Hamiltonian graph, then for any ...
3
votes
1answer
35 views

G is a simple graph with $n$ vertices and $\sum_{v \in V(G)}$$d(v) \choose 2 $$>(m-1)$$ n \choose 2$then G contains $K_{2,m}$

Prove that if G is a simple graph with $n$ vertices and $\sum_{v \in V(G)}$$d(v) \choose 2 $$>(m-1)$$ n \choose 2$then G contains $K_{2,m}$ I tried a proof by contradiction but all it gets me is ...
2
votes
1answer
94 views

Hypergraph terminology

Suppose I have a hypergraph with vertices V and hyperedges H, where each hyperedge is a subset of V. I want to form a normal graph with vertex set V, where two vertices are adjacent if they lie in ...
1
vote
2answers
465 views

Connected graph - 5 vertices eulerian not hamiltonian

i need to give an example of a connected graph with at least 5 vertices that has as an Eulerian circuit, but no Hamiltonian cycle?
2
votes
2answers
200 views

Show that if $|E|\ge |V|$, $G = (V,E)$ contains a cycle.

Show that if $|E|\ge |V|$, the graph $G=(V,E)$ contains a cycle. So I am trying to prove this problem. So I am assuming this is saying that if there are more edges than vertices in G, then G contains ...
2
votes
0answers
105 views

Number of connected bipartite graphs with maximum possible degree

Is there a formula which gives the number of connected bipartite graphs with $n$ vertices such that the degree of every vertex is at most $d$? I can determine the results computationally using nauty, ...
0
votes
1answer
37 views

probability of embeddings in graph

Setup: Let G be a graph on n vertices. Between each pair of vertices, with probability p there is a blue edge, and with probability 1 − p a red edge. Question: Triangle distributions Let T be a ...
2
votes
2answers
132 views

Minimum queens to reach $8 \times 8$ squares as a graph problem

A homework problem asks What is the minimum number of queens to reach all squares on a $8 \times 8$ chess board? We are expected to solve this by somehow casting the problem as a graph problem ...
1
vote
1answer
203 views

Inverse Function + Reflection In Y-Axis

Not getting any of the answers in MC. Is the answer wrong, or have I done something wrong?
2
votes
0answers
62 views

Regarding longest path between nodes in directed graph

Recently I formulated the following problem while solving a question. It has been bugging me since. It is as follows: Given a directed acyclic graph $G$ with $n$ edges, define $l(x,y)$ = longest ...
2
votes
1answer
63 views

Genus of a graph

Let $G$ be a finite simple undirected graph. Suppose we contracted some edges of $G$ to form a new graph $G_1$. Then, is it true that the genus of $G$ is greater than or equal to the genus of $G_1$? ...
2
votes
1answer
355 views

internal nodes in a complete binary tree

Prove or disprove: the number of internal nodes in a complete binary tree of $K$ nodes is $\lfloor K/2 \rfloor$. I tried using induction: Base: 1 node $\rightarrow$ $0$ internal nodes Assumption: ...
5
votes
1answer
56 views

Transforming Nested Fixed-Point Formulas into Infinitary Logic Formulas with Finitely many Variables

There is a definition (actually a description of how it could be defined) of a fixed-point logic formula. The formula is in inflationary fixed point logic (IFP) in this case but it could also be ...
3
votes
1answer
195 views

The library with 999 books.

In the town of Capibara there is a library with books in 999 themes. Since Capibara is an international town they have books in various languages. We know that for every language we can find exactly ...
2
votes
1answer
67 views

Generating Eulerian digraphs/isographs

I would like to be able to quickly generate (all) non-isomorphic isographs (that is, digraphs where each node has the same indegree and outdegree - also called "balanced networks" in the distributed ...
1
vote
1answer
133 views

Maximizing edges in directed acyclic graph

Question: What is the maximum number of edges in a non-transitive directed acyclic graph on $n$ vertices? Here nontransitive means, if there is an edge between $A$ and $B$, and an edge between $B$ ...